Məsələlər
Золото дядюшки Скруджа
Золото дядюшки Скруджа
Дядюшка Скрудж изготовил множество золотых слитков и пронумеровал их последовательностями из нулей и единиц длины 2n - 2 (номер каждого слитка выбит на нём). Известно, что
- Любые два слитка имеют различные номера.
- В номере любого из слитков не встречается двух нулей подряд.
- Для любой последовательности, отвечающей свойству 2, слиток с таким номером есть в коллекции дядюшки Скруджа.
Затем дядюшка Скрудж решил разложить слитки по сейфам. Коды к сейфам подобраны схожим образом с номерами слитков. А именно
- Код к сейфу является последовательностью из нулей и единиц длины n - 2.
- Коды к любым двум сейфам различаются.
- В коде ни одного из сейфов не встречается двух нулей подряд.
- Для любого кода, отвечающего свойствам 1 и 3, сейф с таким кодом стоит в хранилище дядюшки Скруджа.
Дядюшка Скрудж положил в каждый из сейфов одинаковое количество золотых слитков, а оставшиеся слитки (их осталось меньше, чем сейфов) решил отправить на благотворительность. Найдите, сколько слитков лежит в каждом из сейфов дядюшки Скруджа.
Входные данные
Целое число n (3 ≤ n ≤ 70000).
Выходные данные
Выведите количество слитков в каждом из сейфов.
Giriş verilənləri #1
3
Çıxış verilənləri #1
4