{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/c7d8baf2d093454f7b7019615646a180?v\u003d1713911109\" alt\u003d\"/problems/scaffolding/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eBamboo scaffolding is very popular in Hong Kong. It is\n widely used in construction and maintenance of buildings, when\n high temporary structures are built to hold construction\n workers. You will also find bamboo scaffolds in Cantonese opera\n theatres and at the Bun Scrambling Competition in Cheung Chau.\n\n \u003cp\u003eAs a construction worker, you want to build a bamboo\n scaffold for an upcoming festival. There are specific\n requirements for the final scaffold, which will be part of a\n vertical, \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e-dimensional\n grid. \u003cspan class\u003d\"tex2jax_process\"\u003e$N+1$\u003c/span\u003e vertical long\n bamboos are already established, so there are \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e columns in between. Initially all\n columns are empty. Our task is to place exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$H_ i$\u003c/span\u003e horizontal short bamboos in the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth column, literally\n from the ground up.\u003c/p\u003e\n\n \u003cdiv id\u003d\"a0000000004\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/61a3a64f037db7a0244617b057ea9cf5?v\u003d1713911109\" alt\u003d\"\\includegraphics[width\u003d.95\\textwidth ]{diagrams}\" style\u003d\"width:95.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: The left diagram illustrates the initial\n scaffold that has \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e empty columns. The right\n diagram shows the final scaffold for Sample Input 2.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003eYou can carry at most \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e short bamboos at a time. You will\n install the short bamboos in a number of rounds. In each round,\n you take at most \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e short\n bamboos with you, and start anywhere on ground level.\u003c/p\u003e\n\n \u003cp\u003eYou can only stand on a short bamboo that was built\n previously (or on ground level). Then you have two options:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eClimb left, right or up if a short bamboo is already in\n place there\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003ePlace a short bamboo to the left, right or up if there\n is no short bamboo already placed\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eNote that you cannot go down while carrying short bamboos.\n You cannot place a short bamboo below you either.\u003c/p\u003e\n\n \u003cp\u003eOnce you finish placing all the short bamboos in the current\n round, you go down to the ground level. You then take at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e short bamboos with you\n and start another round from the ground level. This goes on\n until you have built the desired scaffold, with exactly\n \u003cspan class\u003d\"tex2jax_process\"\u003e$H_ i$\u003c/span\u003e short bamboos in\n column \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e for all\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eWhat is the minimum number of rounds you need?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line contains two integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq N \\leq 100\\, 000$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq M \\leq 10^9$\u003c/span\u003e). The second line contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$H_1, \\dots , H_ N$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq H_ i \\leq 100\\, 000$\u003c/span\u003e).\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput an integer representing the minimum number of\n rounds.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\n2 1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 10\n2 1 2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}