{"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 div.sampleinteractionread {\n width: 60%;\n margin: 3px 0px 3px 0px;\n }\n div.sampleinteractionread pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n div.sampleinteractionwrite {\n width: 60%;\n margin: 3px 0px 3px 0px;\n margin-left: auto;\n }\n div.sampleinteractionwrite pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n table.sample {\n width: 100%;\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:25.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/7d2caa7bfaabba2bfd0e79e292e0259c?v\u003d1726147444\" alt\u003d\"/problems/incrementalinduction/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eThe Nordic Collegiate Pong Championship (NCPC) is an\n insanely competive tournament where every contestant plays\n exactly one game of Pong against every other contestant. The\n last game of the tournament just finished, so only one item now\n remains on the programme: the traditional diploma ceremony,\n where all this year’s participants get inducted into the NCPC\n Hall of Fame.\n \u003cp\u003eAccording to the ancient customs, contestants who have not\n been inducted into the Hall of Fame yet (the pathetic nobodies)\n must stay on the left side of the stage, whereas contestants\n who have been inducted (the awesome legends) must be on the\n right side of the stage. Then, when a contestant is receiving\n their diploma, they will symbolically walk from the left to the\n right side of the stage and thus become an awesome legend. Only\n one contestant is inducted into the Hall of Fame at a time, and\n every contestant starts on the left side initially.\u003c/p\u003e\n \u003cp\u003eThe NCPC Head of Jury believes it reflects badly on her if\n too many of the awesome legends on the right have lost matches\n against pathetic nobodies on the left, but she quickly realizes\n that it might be impossible to avoid this at every point in\n time during the diploma ceremony. However, she certainly wants\n to keep such atrocities at a minimum. Specifically, she wants\n to find the smallest number \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e for which there exists an order of\n handing out diplomas to the contestants, such that at no point\n there were more than \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e\n games played where an awesome legend lost against a pathetic\n nobody.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 5\\, 000$\u003c/span\u003e), the number\n of contestants. Then follows \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines, the \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{\\text {th}}$\u003c/span\u003e of which contains a\n binary string of length \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^{\\text {th}}$\u003c/span\u003e character on the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{\\text {th}}$\u003c/span\u003e line is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e if contestant\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i+1$\u003c/span\u003e defeated contestant\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e if contestant \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e defeated contestant \u003cspan class\u003d\"tex2jax_process\"\u003e$i+1$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single integer \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e, the smallest number according to\n the requirements above.\u003c/p\u003e\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\n1\n01\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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\n0\n00\n100\n1100\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 "}}]}