Семнадцатый день школы Юниор

Результаты в самом конце. О награждении будет отдельно.

Заключительный контест из 11 задач

Продолжительность контеста - 2 часа. Задач для столь короткого контеста слишком много. Просто хотелось дать слушателям школы возможность выбора. Но слушатели этой возможностью не воспользовались. Правда, Руслан обнаружил простую на вид задачу K про количество счастливых билетов. К сожалению, решение "в лоб" для 8 цифр не прошло по времени, слишком много операций деления. Это типичная олимпиадная задача, ее решение легко найти в Интернете.  И Алексей Доронин взялся за задачу B. Скобки (на стек), но не удачно.

Затем Никита решил самую простую на контесте задачу D. Ягодники и через несколько минут Артур решил задачу F. Бронзовый призер (сортировка), после чего все приступили к решению этих задач. Руслан тем временем добил задачу Е. Максимум из минимумов. Никита смог с ней справиться почти на час позже. Но для Никиты это была уже третья задача.

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

A. Забавная игра

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик - он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011
...
и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28. Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Ввод
Ввод содержит одно целое число N (0 ≤ N ≤ 32767).
Вывод
Ваша программа должна вывести одно целое число, равное результату игры.

B. Скобки

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

Ввод
В первой строке находится число скобок N, во второй N символов из набора (, ), [, ], {, }.
Вывод
Выводится слово "Yes", если получить правильное арифметическое выражение можно, или "No", если нельзя.
Ограничения
1 ≤ N ≤ 100 000.

C. Скоро лето

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

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

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

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

Формат ввода:

В первой строке находятся два целых числа N и M (0 < N, M ≤ 1000) — размер сетки кварталов с запада на восток и с юга на север соответственно. Математик начинает путь с перекрёстка, который находится к юго-западу от квартала с координатами (1, 1); вход в лес находится к северо-востоку от квартала с координатами (N, M). Во второй строке находится целое число K (0 ≤ K ≤ 100) — количество кварталов, через которые можно пройти наискось. Далее следуют K строк с парами целых положительных чисел, разделённых пробелами — координатами таких кварталов.

Формат вывода:

Требуется вывести длину кратчайшего пути от дома математика до леса в метрах, округлённую до целых метров.

D. Ягодники

Шли как-то два математика по лесу и собирали ягоды. Час шли, два шли, а потом вдруг остановились и решили ягодами помериться. Достали они весы (какой же математик пойдет в лес без весов?) и взвесили свои корзины с собранным урожаем, а потом записали полученные числаa₁ и b₁ на листочек. После этого второй математик пересыпал все ягоды в корзину к первому (полностью опустошив свою корзину), и они снова взвесили свои корзины, получив числа a₂ и b₂ соответственно. Наконец, первый математик пересыпал все ягоды в корзину ко второму (полностью опустошив свою корзину); после взвешивания они получили числа a₃ и b₃ соответственно. Этих данных оказалось достаточно для определения победителя, и довольные математики пошли дальше. Вам же предстоит вычислить массу ягод в корзине каждого из математиков до совершения всех пересыпаний.

Формат ввода:

Входные данные состоят из трёх строк. В i-й строке (1 ≤ i ≤ 3) записаны целые числа a_i и b_i (0 ≤ a_i, b_i ≤ 10 000).

Формат вывода:

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

Е. Максимум из минимумов

Задана матрица X[1..M, 1..N] целых чисел (1 ≤ M, N ≤ 100). Все числа в матрице различны. В каждой строке находится минимальный элемент, затем среди этих чисел выбирается максимальное. Составьте программу, находящую номер строки матрицы X, в которой расположено выбранное число.

Ввод

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

Вывод

Выведите одно число - номер строки в которой содержится максимум из минимумов.

F. Бронзовый призер

В соревнованиях по бегу принимают участие N спортсменов (3 ≤ N ≤ 1000). Результаты забега занесены в массив по порядку номеров участников. Все результаты участников различны. Определить время (результат) бронзового призёра.

Ввод

Первая строка содержит N - количество участников забега. Следующая строка содержит результаты каждого участника забега (через пробел) в последовательности номеров участников.

Вывод

На экран выводится время (результат) бронзового призёра.

G. Вирусы

На поле размером N*N расположено M вирусов. За каждый ход вирус заражает 4 соседние с ним клетки. Положение вирусов задано координатами на поле. Требуется написать программу, определяющую, за какое наименьшее количество ходов будет заражено все поле.

Ввод

В первой строке записаны два числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 10). Каждая из следующих M строк содержит по два числа - координаты вируса на поле. Все числа целые, координаты по величине не превосходят размеров поля. Левая нижняя клетка поля имеет координаты (1, 1).

Вывод

В первую и единственную строку выведите одно число - искомое наименьшее количество ходов.

H. Редкое имя

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

Ввод

Список учащихся школы. В каждой строке через пробел заданы Фамилия Имя и Отчество ученика. Требуется определить, какое имя самое редкое. Число учеников в школе ≤ 10000.

Вывод

Одна строка с искомым именем.

Ввод	Вывод
Пушкин Александр Сергеевич Луканов Александр Сергеевич Соколова Любава Викторвна Иванов Иван Иванович Сидоров Иван Петрович	Любава

I. Перестановки

Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.

Ввод

В первой строке файла находится исходная строка.

Вывод

Вывести в каждой строке файла по одной перестановке. Перестановки можно выводить в любом порядке. Повторений и строк, не являющихся перестановками исходной, быть не должно.

Ограничения

2 ≤ M ≤ 8; символы - буквы латинского алфавита и цифры.

Ввод 1	Ввод 2
AB	IOX
Вывод 1	Вывод 2
AB BA	XOI OIX IXO XIO OXI IOX

J. Почтовые цифры

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

Проанализируйте число на вводе и выведите максимальную цифру этого числа.

Ввод

Начиная с первой строки записаны цифры в анализируемом числе. Количество цифр: 1 ≤ n ≤ 10. Каждая цифра занимает 5 столбиков. Цифры отделяются друг от друга столбиком из пробелов. Последним символом в каждой строке записана точка. Таким образом, число в файле занимает 9 равных по длине строк, каждая из которых содержит звездочки, пробелы и точку в конце. Длина каждой строки равна 6*n.

Вывод

Необходимо вывести одну обычную десятичную цифру.

Ввод

***** *   * *****     *.    *  *   * *        * .   *   *   * *       *  .  *    *   * *      *   . ***** ***** ***** *****.    *      *     * *   *.   *       *     * *   *.  *        *     * *   *. *         * ***** *****.

Вывод

6

K. Счастливые билеты

Имеется лента билетов с восьмизначными номерами. Первый билет имеет номер M, последний – N. Величины M и N отвечают следующему соотношению: 10000000 ≤ M < N ≤ 99999999. Необходимо определить количество "счастливых" билетов в ленте. Билет считается "счастливым", если сумма первых четырех цифр равна сумме последних четырех цифр.

Ввод
Ввод содержит построчно номера первого и последнего билетов в ленте.
Вывод
Необходимо вывести искомое количество "счастливых" билетов в ленте.

Ввод 1	Ввод 2
11111110 11111112	10000000 99999999
Вывод 1	Вывод 2
1	4379055

Результаты контеста ЮНИОР 3 

14 июля. Продолжительность 2 часа.

R	Участник	A	B	C	D	E	F	G	H	I	J	K	+	T
1	Холопов Никита				+1 00:41	+3 01:56	+ 00:52						3	289
2	Крючков Артур				+ 01:23		+ 00:45						2	128
3	Доронин Алексей		-1 00:28		+ 01:19		+ 01:07						2	146
4	Селезнёв Руслан				+ 01:03	+2 00:55						-3 00:17	2	158
5	Тропин Иван				+ 01:09		+2 01:33						2	202
6	Иванов Максим				-1 00:23		+ 00:58					-2 01:40	1	58
7	Литовченко Алексей				+1 01:01		-1 01:55						1	81
Попыток		0	1	0	9	7	8	0	0	0	0	5
Из них зачтено		0	0	0	6	2	5	0	0	0	0	0
Не зачтено		0	1	0	3	5	3	0	0	0	0	5