Уважаемый участник олимпиады!
В связи с автоматизированной проверкой работ, жюри убедительно просит соблюдать следующие технические требования:
· Программы следует сохранять в файлах с именами заданного формата: длина имени — семь символов, из них первый символ — Z, второй символ — номер зоны, третий — символ _ подчеркивания, четвёртый и пятый символы — регистрационный номер участника, шестой — символ _ подчеркивания, седьмой символ — номер задачи. Расширение имени файла — .PAS или. BAS, в зависимости от используемой среды программирования. Например, участник зонального тура в пятой зоне, зарегистрированный под номером №9, Pascal-программу решения первой задачи должен сохранить в файле с именем Z5_09_1.PAS
· Имена дисковых файлов, содержащих входные и выходные данные, в программе следует записывать без указания диска и пути по каталогам, то есть должно быть записано только собственное имя файла: INPUT. TXT или OUTPUT. TXT.
· Следует строго соблюдать предписанный в заданиях формат вывода результатов.
· Ограничение по времени тестирования задано в расчете на использование процессора с тактовой частотой не менее 800 Мгерц.
1. Театр (20 баллов)
В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые зрители опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.
В антракте один из опоздавших решил сесть на свое место. Если его место до этого было занято, то сидевший там пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место, и так далее. Поскольку в театр попали только зрители с билетами, то начавшийся в антракте процесс пересаживания зрителей обязательно заканчивался.
Требуется составить программу для подсчета количества зрителей, которые были вынуждены пересесть на свои места.
Технические требования:
Входной файл: INPUT. TXT.
Выходной файл: OUTPUT. TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT. TXT состоит из трех строк. В первой строке содержится целое число N (1 £ N £ 15 000) — количество мест в театре. Вторая строка содержит последовательность из N целых чисел, разделенных пробелами. Первое число определяет номер места в билете у зрителя, занявшего первое место, второе число — номер места в билете у зрителя, занявшего второе место, и так далее. Если место свободно, то соответствующее число равно 0. Третья строка содержит одно целое число K (1 £ K £ 15 000) — номер места в билете опоздавшего зрителя, который решил пересесть в антракте на свое место.
Формат выходных данных:
Выходной файл OUTPUT. TXT содержит одно целое число — количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.
Примеры файлов входных данных: | Примеры файлов выходных данных: |
8 5 | 3 |
10 0 0 2 | 0 |
2 2 1 1 | 2 |
2. Лыжники (25 баллов)
В лыжных гонках участвовало N спортсменов, которые стартовали в разное время, но в порядке возрастания номеров от 1 до N. Каждый лыжник запомнил, сколько ранее стартовавших прибежали после него.
Требуется составить программу, определяющую порядок, в котором спортсмены прибежали к финишу.
Технические требования:
Входной файл: INPUT. TXT.
Выходной файл: OUTPUT. TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Первая строка файла INPUT. TXT содержит целое число N (1 £ N £ 1 000) — количество лыжников. Вторая строка содержит N целых чисел K1, K2, ... , KN, разделенных пробелами, Ki — количество спортсменов с номерами меньше i, которые пришли к финишу после i-го лыжника.
Формат выходных данных:
Выходной файл OUTPUT. TXT содержит N целых чисел — номеров спортсменов, определяющих порядок, в котором они пришли к финишу. Все числа разделяются пробелами.
Пример файла входных данных:
5
Пример файла выходных данных:
3. Яблоневый Сад (30 баллов)
Однажды отец позвал двух своих взрослых сыновей и сказал: «Я постарел, и мне трудно ухаживать за нашим садом. Поэтому я решил поделить сад между вами. Мы разгородим его забором по линии, проходящей от крыльца дома к калитке сада. Старшему сыну достанется правая от входа часть сада, а младшему — левая. Яблони, растущие на расстоянии менее трех метров до нового забора, придётся срубить, чтобы не бросали тень на соседний сад».
Требуется составить программу, которая определяет, сколько яблонь достанется старшему и младшему сыну.
Технические требования:
Входной файл: INPUT. TXT.
Выходной файл: OUTPUT. TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Расстояние от яблонь до забора определять с точностью до 1 см.
Формат входных данных:
Первая строка входного файла содержит четыре разделённых пробелами действительных числа — координаты крыльца и калитки сада (в метрах).
Последующие строки (их не более 10 000) содержат по два разделённых пробелами действительных числа — координаты яблонь (в метрах). Все числа по абсолютной величине не превосходят 10 000.
Формат выходных данных:
Единственная строка выходного файла содержит два разделённых пробелом целых числа — количества яблонь, доставшихся старшему и младшему сыну.
Пример файла входных данных:
Пример файла выходных данных:
1 2
4. Путешествие (35 баллов)
В стане N городов. Между любыми двумя из них проложена только одна дорога: либо автомобильная, либо железная. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие.
Требуется составить программу для нахождения города, с которого турист должен начать путешествие, и один из маршрутов так, чтобы ему пришлось поменять вид транспорта не более одного раза.
Технические требования:
Входной файл: INPUT. TXT.
Выходной файл: OUTPUT. TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Первая строка файла INPUT. TXT содержит целое число N — количество городов в стране (3 £ N £ 100). Следующие N строк описывают порядок соединения городов железными дорогами. Каждая i-ая из них содержит номера городов, соединенных с i-ым городом железной дорогой. В этой строке записано единственное число 0, если из i-ого города не выходит ни одной железной дороги. Все числа разделены пробелами.
Остальные дороги между городами — автомобильные.
Формат выходных данных:
Если решения не существует, выходной файл OUTPUT. TXT содержит число 0. Если решение существует, выходной файл OUTPUT. TXT содержит описание требуемого маршрута — последовательность из N + 1 разделенного пробелами чисел (номеров городов). Первое и последнее числа должны совпадать — они задают номер города, с которого турист должен начать и в котором должен закончить свой маршрут.
Пример файла входных данных:
2 | 3 | |
1 | 4 | |
4
2 3 4
1 4
1
1 2
Пример файла выходных данных:
