e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Evolution (RU)

Evolution (RU)

Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.

2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).

3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.

4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на n-ом шаге.

prb223

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.

Входные данные

Первая строка содержит количество этапов эволюции n(1 n 100), которые произошли на планете Олимпия до текущего времени. Вторая и третья строки содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

Выходные данные

Вывести одно натуральное число - номер ближайшего предка для двух видов.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
4
15
12
Output example #1
3
Input example #2
18
233016
233008
Output example #2
14563
Author Daniil Neiter
Source 2009 XXII All-Ukrainian Informatics Olympiad, Khmelnytskiy, March 22 - 27, Round 2