eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Еволюція

Еволюція

Під час досліджень, присвячених появі життя на планеті Олімпія, вченими було зроблено декілька сенсаційних відкриттів: 1. Усі живі організми планети походять від однієї бактерії \textit{Bitozoria Programulis}. 2.Еволюція проходила крок за кроком (за припущенням вчених -- під час змін клімату на планеті). 3.На кожному кроці еволюції з кожного виду утворювалися рівно два підвиди, а попередній вид зникав. 4.Якщо вважати появу бактерії \textit{Bitozoria Programulis} першим кроком еволюції, то нині існуючі живі організми знаходяться на \textbf{n}-му кроці. \includegraphics{https://static.e-olymp.com/content/ab/ab840eb5b3239edce50560448c983922f2447299.jpg} Щоб не вигадувати назви під час досліджень, вчені пронумерували всі види організмів, що будь-коли існували на планеті. Для цього вони намалювали дерево еволюції із коренем \textit{Bitozoria Programulis}, яка отримала номер \textbf{1}. Далі нумерували види кожного кроку еволюції зліва направо. Таким чином безпосередні підвиди \textit{Bitozoria Programulis} отримали номери \textbf{2} та \textbf{3}. Наступними були занумеровані види третього кроку еволюції -- підвиди виду \textbf{2} отримали номери \textbf{4} та \textbf{5}, а виду \textbf{3 - }номери \textbf{6 }та \textbf{7}, і т.д. Напишіть програму, яка за номерами двох видів обчислить номер виду їх найближчого спільного предка у дереві еволюції. \InputFile Перший рядок містить кількість етапів еволюції \textbf{n }(\textbf{1 }≤\textbf{ n }≤\textbf{ 100}), що відбулися на планеті Олімпія до теперішнього часу. Другий та третій рядки містять по одному натуральному числу, що представляють номери видів, для яких потрібно знайти номер їх найближчого спільного предка. \OutputFile Вивести одне натуральне число - номер найближчого предка для двох видів.
Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
4
15
12
Вихідні дані #1
3
Вхідні дані #2
18
233016
233008
Вихідні дані #2
14563
Автор Даниїл Нейтер
Джерело 2009 XXII Всеукраїнська олімпіада з інформатики, Хмельницький, Березень 22 - 27, тур 2