Прошло много лет после событий предыдущих задач, и Карен уже закончила учиться и собирается переехать в новый район.
Район состоит из n домов, расположенных на прямой, пронумерованных от 1 до n слева направо, с равными расстояниями между ними.
Каждый в этом районе любит тишину и покой. Поэтому когда новый житель переезжает сюда, он выбирает такой дом, что минимальное расстояние до любого из занятых домов является максимально возможным. Если домов с максимально возможным минимальным расстоянием несколько, житель выбирает самый левый из них.
Обратите внимание, что первый житель всегда выбирает дом номер 1.
Карен будет k-м по счету жителем этого района. Если все, включая ее, следуют вышеописанному правилу, в какой дом переедет она?
Примечание
В первом примере в районе 6 домов, и Карен — четвертый по счету житель.
- Первый житель выберет дом 1.
- Второй житель выберет дом 6.
- Третий житель выберет дом 3.
- Четвертый житель выберет дом 2.
Во втором примере в районе 39 домов, Карен — третий по счету житель.
- Первый житель выберет дом 1.
- Второй житель выберет дом 39.
- Третий житель выберет дом 20.