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

Он изготовил трафарет NxN клеток (N — четное), в котором вырезал клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.

Пример такого трафарета показан на рисунке ниже:

С помощью этого трафарета шифруется текст из N² символов следующим образом. Сначала в прорези трафарета вписываются первые букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:

Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N² символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.

Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:

При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:

При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):

После этого получившийся текст Петя выписывает в строчку:

О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0

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

Напишите программу, которая для данного трафарета определит, после какого наименьшего количества процедур шифрования Петя получит исходный текст независимо от содержания текста?

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 2₁₀ = 10₂, 24₁₀ = 11000₂.

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

Вася любит искать во всём закономерности. В его тетрадке записаны три числа A,B и C, и он хочет установить между ними какую-нибудь простую закономерность. Для начала он хочет узнать, можно ли этим числам приписать в конец несколько нулей так, чтобы сумма первых двух чисел стала равна третьему. Например, если у него записаны числа 9,34 и 43, то он может не приписывать к ним нулей сумма 9 и 34 и так равна 43. Если же у него записаны числа 23, 7 и 93, то он может приписать нуль к 7 и получить 70. После чего 23 + 70 = 93. Вам дано три натуральных числа A,B и C. Требуется найти неотрицательные целые числа n, m и k, такие что A × 10ⁿ + B × 10^m = C × 10^k.

«Что наша жизнь? Игра!»

Вася в казино играет в интересную игру.

Сначала он платит вступительный взнос за игру и в обмен на деньги получает право играть. Более того, за уплаченные деньги он сразу получает X очков.

На автомате, в который он играет, есть три кнопки. Когда он нажимает первую, к его очкам добавляется A очков. Когда нажимает вторую — добавляется B. Когда нажимает третью — добавляется C очков.

Ему разрешается сначала несколько раз (или ни разу) нажать третью кнопку, и затем несколько раз (или ни разу) — первую. Нажимать вторую кнопку Васе запрещено.

Если после этого он набрал ровно Y очков, то Вася считается выигравшим, и ему выплачивается премия. Если же Y очков набрать не удается, Вася считается проигравшим, и ничего не получает.

Если Вася выиграл, то считается, что он разгадал одну из волшебных последовательностей нажатий, которые приводят к выигрышу. Он имеет право и дальше играть в эту игру, и искать другие такие последовательности, которые X очков превращают в Y, но ему категорически запрещено использовать одну и ту же выигрышную последовательность более одного раза.

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