Возвращаясь из школы домой, Петя каждый раз обращал внимание на надпись на заборе «1 + 1 = 10» и удивлялся очевидной его неправоте. Но однажды его осенило, что это равенство верное, если рассматривать его в двоичной системе счисления. Его настолько поразила эта идея, что он решил непременно придумать свои три числа так, чтобы сумма первых двух была равна третьему в некоторой системе счисления.

Теперь он перебирает тройки чисел, которые, на его взгляд, достойны находиться на заборе. Петя выбирает числа A, B, C, записывающиеся десятичными цифрами, и дальше пытается найти основание системы счисления K, в которой равенство A + B = C оказалось бы верным. Петя рассматривает системы счисления с основанием от 2 до бесконечности.

Поскольку проверка каждой тройки — занятие трудоемкое, в помощь Пете необходимо написать программу, облегчающую расчеты.

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

1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

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

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

Один из самых простых способов обогащения предложили писатели-фантасты. Он заключается в следующем: берем исправную машину времени и с ее помощью отправляемся в прошлое на несколько веков. Там помещаем небольшую (но лучше все-таки побольше) сумму денег в банк под сколько-то процентов годовых. Потом возвращаемся в настоящее, идем в филиал сохранившегося банка и предъявляем ценные бумаги к оплате.

Напишите программу, которая вычислит сумму на счете, скопившуюся за \(N\) (натуральное, не превышает 2000) лет при 10% годовых при начальном взносе равном \(X\) (натуральное, не превышает \(10^6\)). Проценты начисляются следующим образом: по прошествии каждого года к сумме, находящейся на счете, прибавляется 10% от нее, округленные до целого в меньшую сторону.

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

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Проигрывает тот, кто не может сделать ход.

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