{"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 \u003cp\u003eYou are stuck at a boss level of your favourite video game.\n The boss battle happens in a circular room with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e indestructible pillars arranged\n evenly around the room. The boss hides behind an unknown\n pillar. Then the two of you proceed in turns.\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eFirst, in your turn, you can throw a bomb past one of\n the pillars. The bomb will defeat the boss if it is behind\n that pillar, or either of the adjacent pillars.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eNext, if the boss was not defeated, it may either stay\n where it is, or use its turn to move to a pillar that is\n adjacent to its current position. With the smoke of the\n explosion you cannot see this movement.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThe last time you tried to beat the boss you failed because\n you ran out of bombs. This time you want to gather enough bombs\n to make sure that whatever the boss does you will be able to\n beat it. What is the minimum number of bombs you need in order\n to defeat the boss in the worst case? See Figure 1 for an\n example.\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:boss\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/23eea59055032322bbffa19ae104a887?v\u003d1714503311\" alt\u003d\"\\includegraphics[width\u003d0.9\\textwidth ]{fig}\" style\u003d\"width:90.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Example for \u003cspan class\u003d\"tex2jax_process\"\u003e$n\u003d4$\u003c/span\u003e. In this case \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e bombs are enough. Grey\n pillars represent pillars where the boss cannot be\n hiding. The bomb is represented in black.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with a single integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 100$\u003c/span\u003e), the number\n of pillars in the room.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the minimum number of bombs needed to defeat the boss\n in the worst case.\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\u003e4\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\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}