Избыточные строки (100 баллов)

Лепестки роз (100 баллов)

Входные данные: с клавиатуры

Выходные данные: на экран

Ограничение по памяти: 64 мегабайта

Ограничение по времени: 1 секунда

Многим известна логическая игра «Лепестки роз». Напомним суть игры. Играющий бросает 5 игральных костей и говорит число. Остальные игроки пытаются угадать принцип, по которому можно получить этот номер из выпавших игральных костей.

В данной задаче не требуется моделировать эту игру, поскольку это достаточно сложно. Вместо этого мы предположим, что правило подсчета числа известно: сумма точек на каждой выпавшей игральной кости вокруг центральной точки (таким образом, это отдаленно напоминает подсчет количества лепестков розы). Если выпавшая игральная кость не имеет закрашенной центральной точки, то это означает, что у этой «розы» нет «лепестков». Возможные варианты выпадения очков на игральных костях можно видеть на рисунке 1.

Рис. 1. Грани игральной кости

Если на игральной кости выпала одна точка, то в данном случае «лепестков» вокруг центра нет; если две точки, то также нет, поскольку нет центра; если три точки, то количество «лепестков» два; если четыре точки, то «лепестков» нет в виду отсутствия центра; если пять точек, то мы можем найти четыре «лепестка» вокруг центра; наконец, в случае с шестью точками «лепестков» также нет аналогично номерам 2 и 4.

Вам даны значения, выпавшие на игральных костях. Определите количество «лепестков», которые игрок может вычислить в данном случае по правилам, описанным выше.

Яблоки (100 баллов)

Входные данные: с клавиатуры

Выходные данные: на экран

Ограничение по памяти: 64 мегабайта

Ограничение по времени: 1 секунда

Супермаркет «Фрукт» известен тем, что на его прилавках можно найти практически любой товар народного потребления, однако особой славы магазин добился, поскольку имеет в продаже особый сорт яблок – Андреевка.

Система формирования цены в супермаркете также специфическая: одно яблоко особого сорта стоит K рублей, но если покупатель хочет приобрести более одного яблока, то цена второго яблока будет составлять 2 K рублей, третьего - 2² K (4 K) рублей и так далее. В общем случае, если покупатель решил приобрести n яблок, то цена яблока под номером i (1 ≤ i ≤ n) будет составлять 2^i-1 K рублей.

Николай Ежиков очень любит яблоки и поэтому решил приобрести их в супермаркете «Фрукт». Цена купленных яблок вычисляется по формуле, рассмотренной выше. В результате похода в магазин Николай потратил T рублей.

Вам дано число K и сумма, потраченная Николаем (T). Вычислите количество яблок, которое он приобрел. Гарантируется, что при данных K и T ответ всегда существует и он единственный.

Мышка и кошка (100 баллов)

Входные данные: с клавиатуры

Выходные данные: на экран

Ограничение по памяти: 64 мегабайта

Ограничение по времени: 1 секунда

Представьте себе бесконечную трубку, которая имеет круглую форму с радиусом R метров. При этом в ней имеется вход.

В момент времени 0 мышка попадает в данную трубку через вход. Теперь она может бегать внутри нее в двух направлениях (по часовой стрелке и против часовой стрелки), меняя при этом направление своего движения в любой момент времени. Максимальная скорость мышки V_mouse м/c.

В момент времени T секунд через тот же самый вход в трубку попадает кошка, которая также может двигаться в обоих направлениях и изменять направление своего движения в любой момент времени. Также известно, что максимальная скорость кошки V_cat м/с.

Заметим, что мышку и кошку можно считать материальными точками, т.е. их размеры пренебрежительно малы по сравнению с размерами трубки.

Кошка пытается как можно более быстро поймать мышку, которая, в свою очередь, пытается не быть пойманной и, если это невозможно, то быть пойманной максимально поздно. В любой момент времени (начиная с момента времени 0) мышка и кошка знают положение друг друга. Также в момент времени 0 мышка знает время T, через которое в трубке появится кошка. Мышка и кошка ведут себя оптимальным образом.

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

Избыточные строки (100 баллов)

Входные данные: с клавиатуры

Выходные данные: на экран

Ограничение по памяти: 64 мегабайта

Ограничение по времени: 1 секунда

Петя учится в пятом классе и считает себя уже достаточно взрослым, поэтому он решил начать изучать строки. Однако в силу возраста он может изучать не все строки, которые возможны, а только маленькую их часть. В итоге Петя решил остановиться на строках, состоящих из строчных латинских букв «a» и «b».

Сегодня Петя узнал, что строки бывают избыточными и неизбыточными. Строка называется избыточной тогда и только тогда, когда может быть представлена в виде повторения какой-то более короткой строки некоторое число раз. Например, строка «ababab» избыточная, поскольку представляет из себя три копии строки «ab». Строка «ab» называется корнем избыточной строки. Например, строка «aaaa» имеет два корня: «aa» и «a». Также из теории формальных грамматик известно, что каждая избыточная строка имеет ровно один неизбыточный корень (при этом может иметь множество избыточных корней).

Для строк длины n, состоящих из строчных латинских букв «a» и «b», необходимо определить количество избыточных строк, которые также имеют длину n. Петя пока еще недостаточно опытен, чтобы решить такую задачу. Можете ли Вы помочь ему в этом?

Входные данные. На вход программе подается единственное целое число n (1 ≤ n ≤ 60) – длина строк, для которых необходимо найти количество избыточных.

Выходные данные. В результате работы программа должна вывести на экран единственное число – количество избыточных строк длины n.

Примеры.