1. Нам достаточно полстакана…(Брызгалов Е.В., 10 баллов) Группа друзей собралась в понедельник и на все свои деньги купила бутылки с Напитком, не забыв взять сдачу. Во вторник друзья сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько Напитка, сколько могли. Так они действовали до пятницы. В пятницу, сдав посуду и добавив сдачу с четверга, они смогли купить только одну бутылку Напитка.
Требуется определить минимальную сумму, которой располагали друзья в понедельник.
Технические замечания:
Пример работы правильной программы:
Стоимость бутылки с Напитком: 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 баллов). Если вы обратили внимание, то клавиатура многих телефонов выглядит следующим образом:
1 | 2 ABC | 3 DEF |
4 GHI | 5 JKL | 6 MN |
7 PRS | 8 TUV | 9 WXY |
0 OQZ |
Использование изображенных на клавишах букв позволяет представить номер телефона в виде легко запоминающихся слов, что бывает часто более удобно, чем традиционная запись в виде последовательности цифр. Многие фирмы пользуются этим и стремятся подобрать себе номер телефона так, чтобы он содержал как можно больше букв из имени фирмы.
Требуется написать программу, которая преобразует исходный цифровой номер в последовательность букв и цифр, содержащую как можно больше символов из названия фирмы. При этом буквы из названия фирмы должны быть указаны в полученном номере в той же последовательности, в которой они встречаются в названии. Например, если фирма называется IBM, а исходный номер телефона — 246, то его замена на BIM недопустима, тогда как любая из замен на 2IM или B4M является правильной.
Технические замечания:
Пример работы правильной программы:
Введите название фирмы: MEGAPOL
Введите номер телефона: 63542
Новый номер: ME5GA
5. Локомотивы (Каганов И.В., 40 баллов). N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения, локомотивы разобьются на несколько групп, движущихся с разной скоростью. Написать программу, определяющую, сколько начальных расстановок s из N! возможных дадут в результате p групп движущихся локомотивов, 1 <= p <= N.
Предполагается 1 <= N <= 16.
Примечание: при необходимости предполагается доступность типа вещественный двойной точности (double) в используемой системе программирования.