Задача A. Список школ ≡

Условие

При регистрации на портале интернет-олимпиады все участники заполняют регистрационную форму, где они указывают название школы, в которой они учатся. Разные участники могут по-разному писать название школы, например, "Физико-математическая школа №18", "ФМШ №18".

Организаторам олимпиады предоставлена информация о названиях школ, которые написали регистрируемые участники олимпиады. Точно известно, что цифры в названии школы встречаются только в номере школы, а число в записи названия школы встречается ровно один раз и оно однозначно определяет номер школы. Номер школы является положительным целым числом и не может начинаться с нуля.

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

Пояснения к примерам

В приведенном примере для участия в интернет-олимпиаде зарегистрировались: два ученика из школы с номером 18, один ученик из школы с номером 42 и шесть учеников из школы с номером 9. Таким образом, от 1 до 5 участников зарегистрировано от школ с номерами 18 и 42.

Система оценивания

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

Частичные правильные решения для тестов, в которых номера школ –- это числа строго меньше 1000, будут оцениваться из 50 баллов.

Частичные правильные решения для тестов, в которых номера школ –- это числа строго меньше 10⁹, будут оцениваться из 80 баллов.

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

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

Первая строка входного файла содержит одно целое число n -– количество названий школ, указанных всеми участниками при регистрации.

Последующие n строк содержат названия школ, указанные участниками.

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

Первая строка выходного файла должна содержать одно число m -– количество школ, от которых на олимпиаду зарегистрировалось от одного до пяти участников. Последующие m строк должны содержать только номера таких школ, при этом номера должны располагаться по одному в строке в произвольном порядке.

Ограничения

1 ≤ n ≤ 1000

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

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

9
Physics and Mathematics School 18
9ya shkola imeni Pushkina
Lyceum 9
PaMS 18
Gymnasium 42
School 9
Shkola nomer 9
High school 9
School N 9

2
18
42

Задача B. Болезнь ≡

Условие

В Байтландии вспыхнула эпидемия опасной болезни. Известно, что возбудителями болезни являются n различных болезнетворных бактерий.

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

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

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

В первой строке входного файла заданы два числа n (1 ≤ n ≤ 100) — число различных возбудителей болезни и m — число анализов. Следующие m (1 ≤ m ≤ 10 000) строк содержат по n + 1 числу. Первые n чисел описывают, какие возбудители обнаруживаются этим анализом, i-е число равно 1, если анализ проверяет наличие i-го возбудителя и 0 — в противном случае.

Последнее число в строке равно 1, если анализ дал положительный результат, и 0 — в противном случае.

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

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

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

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

3 3
1 0 0 0
1 1 1 1
0 1 0 0

2 1 2
1 3
0

2 2
1 1 0
1 0 1

Incorrect

2 1
1 1 1

0
0
2 1 2

Задача 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