В одной маленькой стране разрешили открывать оффшорные компании, и туда тут же потянулись предприниматели с желанием открыть в ней свою фирму.

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

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

Каждая фирма хочет, чтобы ее телефонный номер было просто запомнить. Если набранное на телефоне название компании соответствует телефонному номеру компании, то номер очень легко запомнить, и ни один клиент его не забудет.

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

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

Она состоит в следующем: Вася берет у дедушки большой кусок фанеры и раскрашивает его так, что у него получается шахматная доска размера N × M клеточек. Потом он берет кости домино и пытается покрыть ими полученную доску так, чтобы все клеточки были закрыты, не было наложений и никакие доминошки не торчали за края доски (каждая доминошка покрывает две соседние клетки).

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

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

Помогите Васе понять, можно ли это сделать.

Красная Шапочка часто навещает свою бабушку. Но она очень боится, что рано или поздно ее бабушку опять навестит волк. Поэтому она решила договориться с Лесничим об охране бабушки. Лесничий согласился охранять бабушку за 10 пирожков.

Узнав об этом, волк сказал Красной Шапочке, что ей совершенно незачем тратить пирожки на Лесничего. За половину тех пирожков, которые Красная Шапочка несет бабушке, Волк пообещал не трогать ее.

26 ноября в России отмечается день матери. Мама испекла несколько пирожков, и попросила Красную Шапочку отнести их бабушке. Требуется определить, какое максимальное количество пирожков Красная Шапочка сможет донести до бабушки.

Несколько школьников решили отпраздновать Новый Год вместе. Для празднования они закупили гору продуктов, и в том числе батон колбасы. Количество еды было настолько велико, что об этом батоне вспомнили только через два с лишним часа после боя курантов. И, конечно, в честь столь знаменательного момента времени школьники решили как можно быстрее съесть этот батон. Но на этом пути их поджидала одна трудность: батон надо разрезать на N (по числу школьников) равных частей, причём как можно быстрее, чтобы не упустить момент. Для этой цели нашёлся очень длинный и острый нож, который смог бы при необходимости разрезать даже N батонов колбасы за один раз. Кроме того, нашлась линейка, с помощью которой можно отмерять любую наперёд заданную часть батона, выбирая место будущего разреза с достаточной точностью. Батон колбасы оказался настолько тонким и длинным, что резать его имело смысл только перпендикулярно его оси.

Конечно, школьники быстро сообразили, что для ускорения процесса можно резать несколько кусков батона одновременно. Батон колбасы оказался прямым и негнущимся, поэтому сэкономить число действий за счёт складывания батона перед разрезанием нельзя. Им осталось определить минимальное количество движений ножом, с помощью которых можно осуществить их намерения. Помогите им в этом. В процессе разрезания школьник может приложить некоторые имеющиеся у него куски батона колбасы друг к другу как он хочет (напомним, что батон очень длинный и тонкий, поэтому имеет смысл прикладывать куски только параллельно друг другу), и одним движением ножа разрезать все куски. Изначально у школьника есть один кусок — сам батон; в конце у него должно быть N одинаковых по длине кусков (каждый длиной в начального батона). Например, разрезать батон на 6 частей (N = 6) школьник может всего за 3 действия ножом:

1. Отмерить длины всего батона и в этом месте разрезать батон.
2. Больший из получившихся кусков разрезать пополам (в итоге получаются три куска равной длины).
3. Приложив их вплотную друг к другу, выровнять концы и разрезать все три куска посередине, в результате чего получится шесть одинаковых кусков.

Чтобы разрезать батон на 5 равных частей (N = 5), также необходимо 3 действия ножом, например:

1. Отмеряем длины батона и разрезаем батон в этом месте.
2. Получившиеся куски складываем вместе так, чтобы середина меньшего куска находилась против трети большего, и разрезаем их так, чтобы меньший разрезать пополам, а больший — в отношении 1: 2. Получаем три куска длиной в всего батона и один — длиной .
3. Больший из имеющихся кусков разрезаем пополам и получаем пять одинаковых кусков.

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

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100- рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам. Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас на маршрутках фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед выездом маршрутки в рейс. Вам дан протокол одного из таких испытаний: известен порядок, в котором пассажиры оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем пассажирам хватило сдачи.