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

Существуют правила, по которым определяется можно ли обрабатывать деталь на определенном станке.

1. Если на текущий момент на станке B было обработано такое же количество деталей, как и на станке A, то следующая деталь должна быть обработана на станке A.
2. В итоге на каждом из станков должно быть обработано одинаковое количество деталей.

Сколько людей, столько и мнений. Каждый из работников этого завода предложил свою последовательность обработки деталей, причем все предложения оказались разными, но удовлетворяющими правилам 1 и 2.

Напишите программу, которая по информации о количестве деталей N определяет максимально возможное количество работников завода.

На кольцевом маршруте суммарной длиной L километров на равном расстоянии друг от друга расположены N остановок (пронумерованных от 1 до N). По этому маршруту движутся M автобусов с одинаковой скоростью v километров в час так, что интервал между двумя идущими друг за другом автобусами один и тот же для всех автобусов (интервалом между автобусами будем называть время, которое проходит между приездом на одну и ту же остановку двух идущих друг за другом автобусов). Автобусы пронумерованы числами от 1 до M. Движение происходит в направлении увеличения номеров остановок.

В некоторый момент времени на всем участке между остановками номер X и Y (не обязательно соседними) начался ремонт дороги, из-за чего скорость движения на этом участке стала w километров в час. Скорость на ремонтируемом участке может оказаться как меньше обычной, так и больше за счет регулировщиков на этом участке дороги. При этом автобусы продолжили движение по маршруту с максимально возможной скоростью (w на ремонтируемом участке и v на остальном). Однако из-за этого интервалы движения между автобусами перестали быть равными.

Если какой-нибудь автобус оказался между остановками X и Y в момент начала ремонта, то он мгновенно меняет свою скорость с v на w, и едет с этой скоростью на протяжении всего ремонтируемого участка. Миновав его, он опять начинает ехать с нормальной скоростью v.

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

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

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим ещё в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от неё. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

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

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

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

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

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

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

Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна a_i рублей b_i копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

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

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

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.