{"id":1422,"date":"2013-03-23T19:03:52","date_gmt":"2013-03-23T11:03:52","guid":{"rendered":"https:\/\/blog.rexdf.org\/?p=1422"},"modified":"2013-03-23T19:03:52","modified_gmt":"2013-03-23T11:03:52","slug":"codeforces-176-b","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/ja\/2013\/03\/codeforces-176-b\/","title":{"rendered":"Codeforces 176 B"},"content":{"rendered":"<div>\n<div>B. Pipeline<\/div>\n<div>\n<div>time limit per test<\/div>\n<p>2 seconds<\/p><\/div>\n<div>\n<div>memory limit per test<\/div>\n<p>256 megabytes<\/p><\/div>\n<div>\n<div>input<\/div>\n<p>standard input<\/p><\/div>\n<div>\n<div>output<\/div>\n<p>standard output<\/p><\/div>\n<\/div>\n<div>\n<p>Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly\u00a0<i>n<\/i>\u00a0houses in Ultimate Thule, Vova wants the city to have exactly\u00a0<i>n<\/i>\u00a0pipes, each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there&#8217;s water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.<\/p>\n<p>A splitter is a construction that consists of one input (it can be connected to a water pipe) and\u00a0<i>x<\/i>\u00a0output pipes. When a splitter is connected to a water pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there&#8217;s water flowing out from it. At most one splitter can be connected to any water pipe.<\/p>\n<p>&nbsp;<\/p>\n<p><center><img decoding=\"async\" class=\"ls_lazyimg\" alt=\"\" src=\"https:\/\/static.rexdf.org\/plugins\/images-lazyload-and-slideshow\/blank_250x250.gif\" file=\"http:\/\/codeforces.ru\/renderer\/fe36a68df20f211fa02a3944a3a69a31cd279b07.png\" \/><noscript><img decoding=\"async\" alt=\"\" src=\"http:\/\/codeforces.ru\/renderer\/fe36a68df20f211fa02a3944a3a69a31cd279b07.png\" \/><\/noscript>The figure shows a\u00a04-output splitter<\/center>&nbsp;<\/p>\n<p>Vova has one splitter of each kind: with\u00a02,\u00a03,\u00a04, &#8230;,\u00a0<i>k<\/i>\u00a0outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it&#8217;s impossible.<\/p>\n<p>Vova needs the pipeline to have exactly\u00a0<i>n<\/i>\u00a0pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.<\/p>\n<\/div>\n<div>\n<div>Input<\/div>\n<p>The first line contains two space-separated integers\u00a0<i>n<\/i>\u00a0and\u00a0<i>k<\/i>\u00a0(1\u2009\u2264\u2009<i>n<\/i>\u2009\u2264\u200910<sup>18<\/sup>,\u00a02\u2009\u2264\u2009<i>k<\/i>\u2009\u2264\u200910<sup>9<\/sup>).<\/p>\n<p>Please, do not use the\u00a0%lld\u00a0specifier to read or write 64-bit integers in \u0421++. It is preferred to use the\u00a0cin,\u00a0cout\u00a0streams or the\u00a0%I64dspecifier.<\/p>\n<\/div>\n<div>\n<div>Output<\/div>\n<p>Print a single integer \u2014 the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.<\/p>\n<\/div>\n<div>\n<div>Sample test(s)<\/div>\n<div>\n<div>\n<div>input<\/div>\n<pre>4 3<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>2<\/pre>\n<\/div>\n<div>\n<div>input<\/div>\n<pre>5 5<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>1<\/pre>\n<\/div>\n<div>\n<div>input<\/div>\n<pre>8 4<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>-1<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<pre class=\"brush: actionscript3; gutter: true\">\r\n#include &lt;iostream&gt; \r\n#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;cmath&gt;\r\n\r\nusing namespace std;\r\n\r\nint main()\r\n{\r\n    long long n,tmp,temp;\r\n    long long k;\r\n    long double dtmp;\r\n    \/\/\u5de8\u90c1\u95f7\uff01\u88ab1000000000 999999999\u53c9\u6389\u4e86\uff0c\u800c\u53ea\u8981\u6362\u6210long double\u5c31OK\u4e86 \r\n    cin&gt;&gt;n&gt;&gt;k;\r\n    tmp=(k-1)*k\/2+1;\r\n    \/\/cout&lt;&lt;tmp&lt;&lt;endl;\r\n    if(n&gt;tmp)cout&lt;&lt;-1&lt;&lt;endl;\r\n    else\r\n    {\r\n        dtmp=(2.0*k-1)*(2.0*k-1)-8.0*(n-1);\r\n        \/\/cout&lt;&lt;dtmp&lt;&lt;endl;\r\n        dtmp=(2.0*k-1-sqrt(dtmp))\/2.0;\r\n        temp=dtmp;\r\n        if(dtmp&gt;temp)temp++;\r\n        \/\/if(dtmp==temp)cout&lt;&lt;&quot;!&quot;&lt;&lt;endl;\r\n        if(dtmp&lt;0)temp=1;\r\n        \/\/cout&lt;&lt;dtmp&lt;&lt;endl;\r\n        cout&lt;&lt;temp&lt;&lt;endl;\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>B. Pipeline time limit per test 2 second &hellip; <a href=\"https:\/\/blog.rexdf.org\/ja\/2013\/03\/codeforces-176-b\/\">\u7d9a\u304d\u3092\u8aad\u3080 <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[125],"class_list":["post-1422","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-codeforces"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1422","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/comments?post=1422"}],"version-history":[{"count":0,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1422\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/media?parent=1422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/categories?post=1422"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/tags?post=1422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}