Задача A. Памятка водителю ≡

Условие

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

Но под конец рабочего дня Авессалому Викторовичу становится трудно быстро вычислять сдачу из-за усталости. Поэтому он решил повесить себе памятку с указанием, сколько давать сдачи на каждую купюру. Известно, что билет стоит N рублей.

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

Формат входного файла

Входной файл содержит целое число N.

Формат выходного файла

Выходной файл должен содержать 4 блока. Для каждого блока необходимо вывести достоинство купюры, за которым должны следовать ноль или более пар целых чисел — количество билетов и сдача при таком количестве билетов. Блоки необходимо вывести по возрастанию достоинства купюры. Пары необходимо вывести по возрастанию количества билетов.

Ограничения

1 ≤ N ≤ 1000.

Примеры тестов

1000

50
100
500
1000
1 0

450

50
100
500
1 50
1000
1 550
2 100

Задача B. Двухцветная полоса ≡

Условие

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

Формат входного файла

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

Формат выходного файла

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

Если существует несколько оптимальных решений, выведите решение с минимальным значением P.

Ограничения

1 ≤ N ≤ 10⁶

Примеры тестов

xxxxx

1 5

abbaaccca

4 6

Задача C. Змейка и ягоды ≡

Условие

Дано поле, состоящее из W × H клеток. Каждая клетка поля либо пустая (обозначается символом '.', ASCII 46), либо содержит ягоду (обозначается символом '*', ASCII 42). Змейка располагается на поле, занимая последовательность клеток так, что каждая следующая клетка этой последовательности смежна по вертикали или горизонтали с предыдущей. Змейка выполняет последовательность шагов по следующим правилам:

• На каждый шаг задано направление движения; направление в следующий шаг времени смениться на прямо противоположное с предыдущим шагом.
• Голова змейки за шаг передвигается на одну клетку в заданном направлении. Остальные части змейки перемещаются каждая на клетку, которую занимала предыдущая часть.
• Если змейка попадает на клетку с ягодой то клетка становится пустой, и количество съеденных ягод увеличивается на единицу.
• После того, как змейка съедает ягоду, она вырастает на одну клетку — на следующий ход, сразу после того, как змейка закончит перемещение, у неё вырастает хвост. Эта новая её часть занимает предыдущую клетку старого хвоста.
• Если змейка выходит за поле или попадает головой на другую свою часть (т.е. самопересекается), игра заканчивается проигрышем.
• Изначально змейка занимает ровно одну клетку. На поле эта клетка обозначена символом '#', ASCII 35.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество тестов в файле. Первая строка каждого теста содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание поля. Далее идёт строка S, каждый символ которой описывает направление движения змейки на очередном шаге:

• L — переместиться на одну клетку влево;
• R — переместиться на одну клетку вправо;
• U — переместиться на одну клетку вверх;
• D — переместиться на одну клетку вниз.

Формат выходного файла

Выходной файл должен содержать N целых чисел, по одному на каждый тест: количество съеденных ягод, любо −1, если игра завершилась проигрышем.

Примеры тестов

2
4 4
....
...#
*..*
..*.
DLDLUR
4 4
....
.#..
*..*
..*.
DLDRD

2
-1

Задача D. Медленное вычеркивание ≡

Условие

Юная любительница математики Маша играет в игру с числами. Сначала она выбирает какое-нибудь целое число S.

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

Это действие повторяется до тех пор, пока не останется число, состоящее из одинаковых цифр.

Юный программист Вася решил произвести впечатление на Машу, запрограммировав её игру.

Требуется написать программу, которая по данному S определяет все числа, получающиеся в процессе игры.

Формат входного файла

Входной файл содержит единственное целое число S.

Формат выходного файла

Выходной файл должен содержать число N — количество чисел, получившихся в игре (не считая исходного S), за которым следует N целых чисел, перечисленных в порядке получения их Машей.

Ограничения

1 ≤ S < 10⁹. В десятичной записи числа S отсутствуют нули.

Примеры тестов

333

0

12524

3
2524
252
22

536296747

6
56296747
6296747
696747
69677
6677
77

Задача E. Удлинители ≡

Условие

В компьютерном классе имеется одна розетка. Для того, чтобы подключить к ней компьютеры, используется N + 1 удлинителей. Один из удлинителей включается розетку, а каждый из остальных N — в другой удлинитель. При этом гарантируется, что каждый удлинитель в конце концов подключен к розетке.

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

Назовём электрическим расстоянием от удлинителя до розетки количество удлинителей, которые должен пройти электрический ток от данного удлинителя до розетки.

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

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

Формат входного файла

Входной файла содержит целые числа N K, за которыми следуют N чисел p_i, где p_i — номер удлинителя, к которому подключен i-й удлинитель, i = 1… N. К розетке подключен удлинитель номер 0.

Формат выходного файла

Выходной файл должен содержать два целых числа S T, означающие, что удлинитель номер S следует отключить от удлинителя номер p_S и подключить к удлинителю номер T. Если оптимальных решений несколько, выведите любое из них.

Ограничения

Примеры тестов

6 2
0 1 2 1 6 0

3 6

1 5
0

1 0