Задачи II-го этапа Всероссийской олимпиады школьников по информатике

(10–11 класс, 2002–2003 учебный год, Пермская область)

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд (на Pentium-100).

1) «Петина практика». (Автор-составитель — Гладков В.П., оппонент — Деменев А.Г.) 10 баллов.
На летней производственной практике Петя Васечкин упаковывал для отправки продукцию предприятия. Он заметил, что в одну коробку помещается A подшипников, в один ящик помещается B коробок с подшипниками, в один контейнер помещается C ящиков, а в один поддон помещается D контейнеров.
Требуется написать программу, определяющую, сколько полных поддонов, контейнеров, ящиков и коробок получится из имеющихся N подшипников, сколько подшипников еще останется. Все данные в задаче помещаются в тип longint..
Формат входных данных:
В единственной строке задаются натуральные числа, разделенные одним пробелом, в следующем порядке: A, B, C, D и N.
Формат выходных данных:
В единственной строке перечисляются через пробел количества полных поддонов, полных контейнеров, полных ящиков, полных коробок и оставшихся подшипников.
Пример файла входных данных:
4 8 12 16 5432
Пример файла выходных данных:
0 14 1 6 0

2) «Особенный момент». (Автор-составитель —  Брызгалов Е.В., оппонент — Шестаков А.П.) 10 баллов.
В течение суток неоднократно встречаются такие особенные моменты времени, что если их записать в формате ЧЧ:ММ:СС, то получится палиндром. Например, 03:00:30 или 12:44:21.
Требуется написать программу, которая по заданному особенному моменту определит следующий за ним особенный момент.
Формат входных данных:
Строка, содержащая особенный момент времени в формате ЧЧ:ММ:CC
Формат выходных данных:
Строка, содержащая особенный момент времени, следующий за данным, в формате ЧЧ:ММ:CC
Пример файла входных данных:
12:55:21
Пример файла выходных данных:
13:00:31

3) «Криптография». (Автор-составитель — Гладков В.П., оппонент — Морозенко В.В.) 20 баллов.

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

Используется бланк ступенчатой формы. Высота первой ступеньки рана двум строкам, последней - N строк. Длины соседних строк отличаются на L. Длина последней ступеньки также равна L. Петя умудрился узнать N и L, используемые при шифровке.

Бланк заполняется текстом (пробел изображается звездочкой, знаки препинания сохраняются) по столбцам, начиная с первого. На рисунке показан вариант заполнения для N=4 и L=2. Если какие-то столбцы не заполнены до конца, они дополняются звездочками.

Затем текст переписывается по строкам и в таком виде передается:
1, 3, 5, 8, 11, 15, 2, 4, 6, 9, 12, 16, 7, 10, 13, 17, 14, 18.
Принятый текст вписывается в такой же бланк по строкам, а считывается по столбцам.

Пример: открытый текст "Privet,*Mary!*How*are*you?"

Заполнение:

Шифртекст: "Pie*rHaorvtMyoru,a!we?****y*"
Требуется написать программу, которая расшифрует заданный шифртекст.
Формат входных данных:
В первой строке вводятся Nи L (3<=N, 1<=L) через один пробел. Во второй строке вводится шифртекст буквами латинского алфавита с сохранением знаков препинания. Слова разделяются звездочками. Неполные столбцы дополняются звездочками. Шифртекст имеет длину не более 255 символов.
Формат выходных данных:
В единственной выходной строке должно быть записано расшифрованное сообщение.
Пример файла входных данных:
5 2
Pie*rHaorvtMyoru,a!we?****y*
Пример файла выходных данных:

Privet,*Mary!*How*are*you?**

4) «Плавные числа».(Автор-составитель — Брызгалов Е.В., оппонент — Немец И.А.) 25 баллов.
Назовем натуральное число плавным, если в его записи соседние цифры отличаются не более, чем на один. Например, число 5445676 является плавным.
Требуется написать программу, которая подсчитает количество натуральных плавных N-значных чисел. (N<20).
Формат входных данных:
Строка, содержащая одно натуральное число N.
Формат выходных данных:
Строка, содержащая количество плавных N-значных чисел
Пример файла входных данных:
2
Пример файла выходных данных:
26

5) «Бочки». (Автор-составитель — Брызгалов Е.В., оппоненты — Белоглазов М.Ю., Муллаханов Р.Х.)  35 баллов.
Во дворе стоят три бочки емкостью P,Q,R литров, первая из них ( емкостью P) заполнена водой, а две остальные пусты.
Требуется написать программу, определяющую минимальное количество переливаний для получения в одной из бочек M литров воды.
За одно переливание можно выбрать одну бочку и переливать её содержимое в другую либо до полного опорожнения первой, либо до полного заполнения второй.
Формат входных данных:
Строка, содержащая четыре натуральных числа P,Q,R и M, не превосходящих 5000 каждое. Числа разделены ровно одним пробелом.
Формат выходных данных:
Одна строка, содержащая либо минимальное количество переливаний, либо фразу «No solution», если решения не существует.
Пример файла входных данных:
8 5 3 4
Пример файла выходных данных:
6