Технические требования:
Входной файл: INPUT.TXT Выходной файл: OUTPUT.TXT
Ограничение по времени: 15 секунд (на компьютере с процессором Pentium-100).
1) «Театр». (Идея — материалы методической комиссии 2001-2002 г., составитель — Брызгалов Е.В., оппонент — Шестаков А.П.) 10 баллов.
В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые из зрителей опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.
В антракте один из опоздавших зрителей решил сесть на своё место. Если его место до этого было занято, то тот, кто там сидел, пересаживался на своё место. Если и там кто-то уже сидел, то и этот зритель также был вынужден вернуться на своё место. И так далее.
Поскольку в театр попали только зрители, имевшие на руках билеты, то начавшийся в антракте процесс пересаживания зрителей обязательно заканчивался. Необходимо определить, сколько человек в результате такого пересаживания были вынуждены поменять свои места.
Требуется написать программу, которая вычисляет количество зрителей, поменявших свои места из-за опоздания одного зрителя.
Формат входных данных:
В первой строке содержится целое число N (N <= 30000) — количество мест в зале.
Вторая строка содержит последовательность из N целых чисел, разделенных пробелами, где первое число определяет номер места в билете у зрителя, который занял место с номером 1, второе — номер места в билете у зрителя, который занял место с номером 2, и так далее. Если место было свободно, то соответствующее число равно 0.
В третьей строке содержится одно число — номер места в билете у опоздавшего зрителя, который в антракте решил пересесть на своё место.
Формат выходных данных:
Одно число — количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.
Пример файла входных данных:
10 0 2 5 3 4 0 0 0 0 0 4
Пример файла выходных данных
3
2) «Умная пчела». (Идея — материалы методической комиссии 2001-2002 г., составитель — Еремин Е.А., оппонент — Брызгалов Е.В.) 15 баллов.
В улье, изображенном на рисунке, ползает пчела. Соты улья представляют собой правильные шестиугольники, поэтому пчела может переползти из одной соты в соседнюю с ней через любую из 6 граней. Каждое направление движения обозначается заглавными латинскими буквами от A до F, как показано на рисунке. При записи пути движения пчелы указывается направление движения и число последовательных переходов, совершенных в этом направлении. Так, например, 4 перехода в направлении B записываются как B4.
Утром пчела начала свой путь и к вечеру оказалась в некоторой точке улья.
Требуется написать программу, которая определяет, за какое минимальное число переходов пчела сможет вернуться в исходную точку, если известна полная запись маршрута.
Технические замечания:
Формат входных данных:
одна текстовая строка, содержащая запись пути пчелы по описанным ранее правилам.
Формат выходных данных:
одна строка, содержащая минимальное число переходов.
Пример 1 входных данных
A1B1C1D1E1
Пример 1 выходных данных
1
Пример 2 входных данных
A33B33C33D33E33F32
Пример 2 выходных данных
1
3) «Последовательность чисел». (Идея — материалы методической комиссии 2001-2002 г., составитель — Гладков В.П., оппонент — Брызгалов Е.В.) 20 баллов.
Рассмотрим бесконечную в обе стороны последовательность целых чисел Fi, в которой для любого целого i элемент Fi+2 вычисляется с использованием следующего условия Фибоначчи: Fi+2 = Fi+1 + Fi. Пусть заданы два различных члена этой последовательности — Fi и Fj с соответствующими номерами i и j, а также некоторое целое число n. Необходимо восстановить элемент этой последовательности Fn, соответствующий номеру n.
Требуется написать программу, которая по заданным числам i, Fi, j, Fj, n вычисляет искомый элемент Fn описанной выше последовательности.
Формат входных данных:
Входной файл содержит в одной строке разделенные пробелом числа: i, Fi, j, Fj, n. Для этих чисел справедливы следующие ограничения:
-1000 <= i, j, n <= 1000;
min(i, j, n) <= k <= max(i, j, n).
Формат выходных данных:
Выходной файл строку, в которой записано искомое число Fn.
Пример файла входных данных:
3 5 –1 4 5
Пример файла выходных данных
12
4) «День консулов». (Автор-составитель — Брызгалов Е.В., оппонент — Шестаков А.П.) 25 баллов.
Звёздная Империя, неуклонно расширяясь, включила в себя уже N (2 <= N <= 20) звездных систем. Каждой системой управляет консул, назначаемый Императором. Однажды Император решил узнать, — был ли в истории Империи день, когда он (или кто-то из его предков) назначил консулов во всех звёздных системах. Для этого он послал запрос в Главный Компьютер и получил для каждой системы даты назначения консулов. Каждый консул управлял системой хотя бы один день (то есть невозможно в один день назначить в одну и ту же систему более одного консула). За всю историю одной системой управляло не более 500 консулов.
Все даты Звездной Империи записываются в формате ДДД.ГГГГ, где ДДД — номер дня, а ГГГГ — номер года (год Империи состоит из 608 дней). Все даты лежат в интервале от 1-го дня 1-го года новой эры (момента образования Империи) до 608-го дня 9999-го года.
Требуется написать программу, которая определяет даты, встречающиеся во всех списках.
Формат входных данных:
Первая строка — N — число систем.
Далее следует N групп строк, которые последовательно содержат:
cтроку с числом консулов i-ой системы;
строки, содержащие даты назначения консулов i-ой системы (даты записаны в формате Империи).
Формат выходных данных:
Строки, каждая из которых содержит дату, когда были проведены назначения во всех системах в хронологическом порядке. Если таких дат нет, то файл содержит одну строку — «No solution».
Пример файла входных данных:
2 3 001.0001 608.9999 017.1978 1 017.1978
Пример файла выходных данных
017.1978
5) «Автобусные маршруты». (Идея — материалы методической комиссии 2001-2002 г., составитель — Брызгалов Е.В., оппонент — Деменев А.Г.) 30 баллов.
Для решения транспортной проблемы в некотором городе до недавнего времени использовались N (N <= 100) автобусных маршрутов. Каждый маршрут начинался на одной из M (M <= 200) площадей и там же заканчивался. В процессе проезда по маршруту автобус мог несколько раз проезжать одну и ту же площадь, но не мог проезжать более одного раза по одной и той же улице в том же самом направлении.
В определенный момент местные власти решили сократить количество автобусных маршрутов в городе до одного. По их мнению, должен был остаться лишь один маршрут, который проходил бы по всем улицам, по которым раньше проходили автобусные маршруты, причем в том же направлении. Если по каким-либо улицам автобусы ездили в обоих направлениях, то и новый маршрут должен проходить по этим улицам в обоих направлениях. По тем улицам и в тех направлениях, по которым раньше автобусы не ездили, новый маршрут проходить не должен. Кроме того, новый маршрут должен удовлетворять всем требованиям старых маршрутов, то есть начинаться и заканчиваться на одной площади, не проходить более одного раза по одной и той же улице в том же самом направлении.
Требуется написать программу, которая для заданных исходных данных определяет требуемый местными властями автобусный маршрут.
Формат входных данных:
Первая строка содержит число N — количество автобусных маршрутов. Далее следует N строк, каждая из которых служит для описания соответствующего автобусного маршрута и содержит сначала число k (k <= 1000), определяющее количество элементов маршрута, а затем k + 1 чисел, задающих номера площадей, которые последовательно проезжает автобус на этом маршруте. При описании маршрута всегда задаются номера первой и последней площадей маршрута, причем они всегда совпадают.
Формат выходных данных:
Либо описание нового маршрута в указанном выше формате, либо одно число 0, если организовать требуемый маршрут невозможно.
Пример файла входных данных:
3 6 1 2 5 7 5 2 1 4 1 4 7 4 1 5 2 3 6 5 4 2
Пример файла выходных данных
15 2 5 4 2 3 6 5 7 4 1 2 1 4 7 5 2
© Пермский областной Оргкомитет олимпиад школьников по информатике, 2001