Эволюция
(Время: 1 сек. Память: 16 Мб Сложность: 32%)
Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:
- Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
- Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
- На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
- Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.
Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.
Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 60) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число – номер ближайшего предка для двух видов.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
15
12 | 3 |
| 2 | 18
233016
233008 | 14563 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
