#1048

Опечатки

Темы: [Строки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2004, 1 день, Задача B ]

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

Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго - удалением буквы "r".

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

Входные данные

В первой строке входного файла через пробел записаны натуральные числа N ≥ 1 - общее количество слов в словаре и M ≥ 1 - количество слов в проверяемом тексте (N+M ≤ 20000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

Выходные данные

Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).

Примеры

Входные данные

5 8
father
and
or
mother
a
Father
and
mather
go
o
for
e
walk

Выходные данные

Father 1 father
and 1 and
mather 2
go 1 or
o 2
for 1 or
e 1 a
walk 0

#1083

Лифт

Темы: [Условный оператор (if)]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача A ]

Чтобы поднять на N-й этаж M-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков производится так: за подъем холодильника на один этаж требуется заплатить 200 рублей, за спуск на один этаж — 100 рублей. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в Витином доме есть лифт, ему возможно все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом K-м этаже, начиная с первого (то есть на этажах с номерами 1, K+1, 2K+1, 3K+1, …). Требуется вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.

Входные данные

Во входном файле записаны три числа: M (2≤M≤100), N (2≤N≤M) и K (2≤K≤M–1), разделенные пробелами.

Выходные данные

В выходной файл выведите одно число — минимальную стоимость подъема холодильника.

Примеры

Входные данные

20 7 4

Выходные данные

Входные данные

20 7 2

Выходные данные

#1084

Маршрутное такси

Темы: [Целые числа]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача B ]

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

Входные данные

Во входном файле записано три натуральных числа, не превосходящих 100 — количества пассажиров в первой, второй и третьей маршрутках соответственно.

Выходные данные

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

Примеры

Входные данные

1 2 3

Выходные данные

Входные данные

99 100 100

Выходные данные

IMPOSSIBLE

#1085

Электропоезд

Темы: [Цикл for]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача C ]

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

Входные данные

В первой строке задано время отправления поезда с начальной станции. Время задается в следующем формате: сначала идут две цифры, задающие часы (от 00 до 23), далее идет двоеточие, затем идут две цифры, задающие минуты (от 00 до 59). Пробелы внутри строки, задающей время, не допускаются.

Во второй строке входного файла записано натуральное число N (2≤N≤1000) — количество станций в маршруте электропоезда (включая начальную и конечную станции). В третьей строке записано N–1 число — первое из этих чисел задает время следования в минутах от начальной станции до второй станции, второе — время от второй станции до третьей и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные

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

Примеры

Входные данные

07:00
4
10 5 3

Выходные данные

Входные данные

22:58
5
2 60 43 20

Выходные данные

#1088

Саморасшифровавшаяся шифровка

Темы: [НОД и алгоритм Евклида] [Цикл for]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача F ]

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

Он изготовил трафарет NxN клеток (N — четное), в котором вырезал клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.

Пример такого трафарета показан на рисунке ниже:

С помощью этого трафарета шифруется текст из N² символов следующим образом. Сначала в прорези трафарета вписываются первые букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:

О				Л
	И		М
				П
		И			А
Д
			А

Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N² символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.

Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:

О	_			Л	П
	И		М	О
		_		П
И		И		Н	А
Д			Ф		О
		Р	А

При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:

О	_	М		Л	П
	И		М	О	А
Т		_	И	П
И	К	И		Н	А
Д		Е	Ф	_	О
	2	Р	А		0

При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

После этого получившийся текст Петя выписывает в строчку:

О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0

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

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

Входные данные

Сначала во входном файле записано число N — размер трафарета (2≤N≤150). Затем идет N² чисел (каждое из которых 0 или 1), описывающих трафарет. 1 обозначает вырезанную клетку, 0 — не вырезанную. Гарантируется, что данная последовательность описывает корректный трафарет для данного способа шифрования.

Выходные данные

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

Примеры

Входные данные

2
1 0
0 0

Выходные данные

Входные данные

6
1 0 0 0 1 0
0 1 0 1 0 0
0 0 0 0 1 0
0 0 1 0 0 1
1 0 0 0 0 0
0 0 0 1 0 0

Выходные данные

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0