1. Нам достаточно полстакана…(Брызгалов Е.В., 10 баллов) Группа друзей собралась в понедельник и на все свои деньги купила бутылки с Напитком, не забыв взять сдачу. Во вторник друзья сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько Напитка, сколько могли. Так они действовали до пятницы. В пятницу, сдав посуду и добавив сдачу с четверга, они смогли купить только одну бутылку Напитка.

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

Технические замечания:

• стоимость бутылки с напитком и пустой бутылки выражаются целыми положительными числами и не превосходят 1000000 лир каждая;


• пустая бутылка дешевле бутылки с Напитком;


• начальная сумма не превосходит 2000000000 лир;


• грамматической согласованностью ответа разрешается пренебречь.

Пример работы правильной программы:
Стоимость бутылки с Напитком: 7
Стоимость пустой бутылки: 3
Достаточно 83 лир

2. “Число в строке” (Деменев А.Г., 15 баллов) Задана строка символов, среди которых есть хотя бы одна цифра. В качестве записи действительного числа будем рассматривать такую подстроку, которая состоит из цифр, возможно разделенных десятичной точкой.

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

Технические требования

Формат входных данных: вводится только одна строка.

Формат выходных данных: выводится только одна строка.

Пример входных данных:
aaa1234.5678.9bbb

Пример выходных данных: 5678.9

3. “Стопами Дирихле”. (Российский Оргкомитет, 20 баллов) У главного животновода кролиководческого хозяйства “Стопами Дирихле” неожиданно возникла проблема. После долгих переговоров с западными партнерами наконец-то поступила партия из 2n кроликов k пород. Кроликов нужно попытаться рассадить в n двухместных клеток, причем это нужно сделать так, чтобы в результате получилось как можно больше однопородных брачных пар (разнополых кроликов, сидящих в одной клетке), а разнопородных брачных пар не было вовсе.

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

Технические требования:

Формат ввода:

f r или m r

где f и m определяют пол кролика (f — самка, m — самец), r — номер породы (целое число от 1 до 10).

Количество кроликов не превышает 100000.

Пример работы правильной программы
Для n = 2, k = 3
f 2
m 3
f 3
m 2
Результат: Хватит клеток. Количество брачных пар — 2

4. Телефонный номер (Российский Оргкомитет, 30 баллов). Если вы обратили внимание, то клавиатура многих телефонов выглядит следующим образом:

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

Требуется написать программу, которая преобразует исходный цифровой номер в последовательность букв и цифр, содержащую как можно больше символов из названия фирмы. При этом буквы из названия фирмы должны быть указаны в полученном номере в той же последовательности, в которой они встречаются в названии. Например, если фирма называется IBM, а исходный номер телефона — 246, то его замена на BIM недопустима, тогда как любая из замен на 2IM или B4M является правильной.

Технические замечания:

• название фирмы — строка из заглавных букв латинского алфавита длиной не более 80 символов, исходный номер — строка из символов от '0' до '9' также не длиннее 80 символов;


• достаточно найти любое оптимальное (содержащее максимальное число символов из названия фирмы) решение.

Пример работы правильной программы:
Введите название фирмы: MEGAPOL
Введите номер телефона: 63542
Новый номер: ME5GA

5. Локомотивы (Каганов И.В., 40 баллов). N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения, локомотивы разобьются на несколько групп, движущихся с разной скоростью. Написать программу, определяющую, сколько начальных расстановок s из N! возможных дадут в результате p групп движущихся локомотивов, 1 <= p <= N.

Предполагается 1 <= N <= 16.

Примечание: при необходимости предполагается доступность типа вещественный двойной точности (double) в используемой системе программирования.

---

---