{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n \u003cdiv\u003e\n \u003cp\u003eThere is a very unusual street in your neighbourhood. This street forms a perfect circle, and the circumference of the circle is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2f528f9e0363b9ee6a6e30b5f8b12c96?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:8.985ex; height:2.176ex;\" alt\u003d\"1\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e. There are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/367c5dacf7f2ffdd724dec89e86a1e3c?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:2.074ex; height:2.176ex;\" alt\u003d\"H\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/66f22f7c003decb224b04d71ae6b5c95?v\u003d1673685775\" style\u003d\"vertical-align: -0.671ex; width:14.544ex; height:2.509ex;\" alt\u003d\"1 \\le H \\le 1\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e) houses on the street. The address of each house is the clockwise arc-length from the northern-most point of the circle. The address of the house at the northern-most point of the circle is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:1.173ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eYou also have special firehoses which follow the curve of the street. However, you wish to keep the length of the longest hose you require to a minimum.\u003c/p\u003e\n \u003cp\u003eYour task is to place \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:1.222ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e (\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e964a65662e952330ef96450a9f46c3d?v\u003d1673685775\" style\u003d\"vertical-align: -0.671ex; width:13.691ex; height:2.509ex;\" alt\u003d\"1 \\le k \\le 1\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e) fire hydrants on this street so that the maximum length of hose required to connect a house to a fire hydrant is as small as possible.\u003c/p\u003e\n \u003ch4\u003eInput Specification\u003c/h4\u003e\n \u003cp\u003eThe first line of input will be an integer \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/367c5dacf7f2ffdd724dec89e86a1e3c?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:2.074ex; height:2.176ex;\" alt\u003d\"H\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e, the number of houses. The next \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/367c5dacf7f2ffdd724dec89e86a1e3c?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:2.074ex; height:2.176ex;\" alt\u003d\"H\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e lines each contain one integer, which is the address of that particular house, and each house address is at least \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:1.173ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e and less than \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2f528f9e0363b9ee6a6e30b5f8b12c96?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:8.985ex; height:2.176ex;\" alt\u003d\"1\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e. On the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fd48da8d8b8ea6a993c087b0f5d9b04a?v\u003d1673685775\" style\u003d\"vertical-align: -0.505ex; width:6.098ex; height:2.343ex;\" alt\u003d\"H+2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003end line is the number \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1673685775\" style\u003d\"vertical-align: -0.338ex; width:1.222ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e, which is the number of fire hydrants that can be placed around the circle. Note that a fire hydrant can be placed at the same position as a house. You may assume that no two houses are at the same address. Note: at least 40% of the marks for this question have \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/061c684f073cc7be0a7892f094400e25?v\u003d1673685775\" style\u003d\"vertical-align: -0.671ex; width:7.529ex; height:2.509ex;\" alt\u003d\"H \\le 10\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\n0\n67000\n68000\n77000\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}