Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
File
...Один – Рогдай, воитель смелый,
Мечом раздвинувший пределы
Богатых киевских полей…
Смелый воитель Рогдай отмечает на кушаке поверженных им соперников (
ну как лётчики-истребители рисовали звёзды на фюзеляже по числу
сбитых самолётов противника). После каждого выигранного поединка
он пришивает к кушаку очередной кусочек, а чтобы не пересчитывать
каждый раз кусочки, когда хочется похвастаться своими победами,
вышивает на кусочке номер.
Хранит Рогдай кушак сложенным. Складывает он его так:
расправляет кушак так, что номера идут слева направо,
берёт правый конец, держа за него, накладывает правую половину
на левую так, что на первое число накладывается последнее.
Затем повторяет эту операцию несколько раз.
Сейчас кушак Рогдая сложен очень аккуратно, все сгибы прошли
по границам кусочков с номерами. Слева сверху на кушаке находится
лоскуток с номером М. Лоскуток с каким номером находится
на кушаке справа сверху? (Гарантируется, что при таких входных данных решение существует)
Входные данные: натуральное число M, не превышающее 1000000,
номер квадратика, находящегося на сложенном поясе слева.
Выходные данные: единственное число – номер квадратика
на правом конце верхнего слоя сложенного кушака.
Для отправки решений необходимо выполнить вход.
|