Общие замечания

• На решение всех задач отводится 5 часов. Участникам предоставляются IBM-совместимые компьютеры (не ниже 386), операционная система DOS или WINDOWS. Разрешается пользоваться литературой и личными записями. Запрещается использовать любую информацию в элекронном виде, приносить свои компьютеры и калькуляторы.
  Решать задачи можно с помощью следующих компиляторов:
  • Borland C++ 3.1
  • Turbo Basic
  • Turbo Pascal 7.0
  • Quick Basic 4.5
  Решением задачи является программа, написанная на одном из допустимых языков и соответствующий исполняемый файл. Разные задачи можно решать на разных языках. Решение 3-й задачи участник номер 8 должен записать в файлы с именами: T08_3.PAS, T08_3.EXE.
• Для каждой задачи у жюри имеется некоторый набор тестов (и способы проверки правильности ответа).
• Жюри оценивает не качество исходных текстов, а качество полученных exe-файлов. Основной критерий, влияющий на набранные очки - количество тестов, правильно выполненных вашей программой. Таким образом, "почти готовая программа", "программа, готовая на 98%" и т.д. не принесут вам очков. Вместе с тем, жюри не исключает при оценке программы обращения к ее исходным текстам.
• В отличие от реальной жизни, все задачи сформулированы абсолютно точно. Если в задаче требуется найти количество каких-либо объектов, то и надо искать только количество. Если вы найдете что-либо дополнительное, например сами объекты, это не принесет вам никаких дополнительных очков.
• Предполагается, что исходные данные к задачам (файлы INPUT.TXT) не содержат ошибок. То есть допустимость и согласованность исходных данных можно не проверять.
• Выходной файл должен иметь в точности ту структуру, что указана в условии задачи. Если в выходном файле, вместе с верным ответом содержится какая-то дополнительная информация, то тест будет считаться не пройденным.
• Обращайте внимание на допустимые значения исходных данных. Если в условии сказано, что число N, задаваемое в файле INPUT.TXT, может принимать значения от 2 до 1222333444, то можете быть уверены, что среди заготовленных жюри тестов имеются такие, у которых N равно как 2, так и 1222333444.
• Не тратьте время на оптимизацию "по мелочам". Если ваша программа уложится не в 5, а в 10 (или даже в 20 секунд) - вам это простят, очки вы не потеряете. Программы, решающие задачу за 0.1 сек и 5 сек будут оценены одним и тем же количеством очков. Если же на некотором тесте время решения ЗНАЧИТЕЛЬНО превышает допустимое - тест считается не пройденным.
• Заранее указать сложность задачи очень трудно. Поэтому количество очков, даваемых за каждую задачу может быть несколько изменено (в зависимости от количества участников, ее решивших).
• Задачи отобраны из предложенных центральным оргкомитетом всероссийской олимпиады для областного тура. Задачи трудные. Жюри на их решение потратило гораздо больше пяти часов. Не обязательно решать все задачи. "Лучше меньше, да лучше".
• Не бросайтесь сразу писать программу. Подумайте.
• Решения жюри окончательны и обжалованию не подлежат

Задача 1. "Автобусные маршруты" (42 балла)

Для решения транспортной проблемы в некотором городе до недавнего времени использовались N (N<=100) автобусных маршрутов. Каждым маршрут начинался на одном из M (M<=200) площадей и там же заканчивался. В процессе проезда по маршруту автобус мог несколько раз проезжать одну и ту же площадь, но не мог проезжать более одного раза по одной и той же улице в том же самом направлении.

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

Требуется написать программу, которая для заданных исходных данных определяет требуемый местным властям автобусный маршрут.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT состоит из следующей последовательности строк. Первая строка содержит число N - количество автобусных маршрутов. Каждая из последующих N строк служит для описания соответствующего автобусного маршрута и содержит сначала число k (k<=1000), определяющее количество элементов маршрута, а затем k+1 чисел, задающих номера площадей, которые последовательно проезжает автобус на этом маршруте. При описании маршрута всегда задаются номера первой и последней площади маршрута, причем они всегда совпадают.

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать либо описание нового маршрута в том же формате, что используется во входном файле, либо одно число 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

Задача 2. "Новобранцы" (28 баллов)

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

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест
Формат входных данных:
Входной файл INPUT.TXT состоит из двух строк. В первой строке этого файла записано число N (1<=N<=30000) - количество солдат в шеренге. Во второй строке содержится последовательность из N символов, каждый из которых может быть либо символом <, либо символом > (символ < означает солдата, повернувшегося налево, символ > - солдата, повернувшегося направо).

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать либо одно число - количество развернувшихся пар, либо слово NO, если процесс бесконечен.

Пример файла входных данных:

6
>><<><

Пример файла выходных данных (для приведенного выше входного файла):

7

В таблице 1 для этого примера приведены расположения солдат в шеренге после очередного завершения разворотов на 180 градусов соответствующих пар солдат.
Таблица 1

Задача 3. "Ломаная" (35 баллов)

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

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест

Формат входных данных:
Входной файл INPUT.TXT состоит из двух строк. В первой строке содержатся два целых числа:
N - размер бумаги в клетку (1 <= N <= 15 );
М - количество звеньев в ломаной (3 <= M <= 20 );
Вторая строка содержит последовательность из M целых чисел, являющихся квадратами длин звеньев ломаной.

Формат выходных данных:
В случае наличия решения данной задачи выходной файл OUTPUT.TXT должен состоять из М строк, в i-ой строке которого содержатся координаты вершин ломаной X_i и Y_i, где X_i, Y_i - целые числа и 0 <= X_i <=N, 0 <= Y_i <=N. Порядок записи координат вершин ломаной в строках должен соответствовать порядку записи квадратов длин звеньев ломаной во входном файле.
В случае наличия нескольких решений следует найти хотя бы одно из них. Если по исходным данным ломаную восстановить не возможно, то выходной файл должен содержать сообщение "Нет решения".

Пример файлов входных и выходных данных:

INPUT.TXT       OUTPUT.TXT
8 4             0 1
13 29 37 5      3 3
                8 1
                2 0

INPUT.TXT       OUTPUT.TXT
8 4             Нет решения
1 1 1 2

Задача 4. "Театр" (21 балл)

В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые из зрителей опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.

В антракте один из опоздавших зрителей решил сесть на свое место. Если его место до этого было занято, то тот, кто там сидел, пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место. И так далее.

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

Требуется написать программу, которая вычисляет количество зрителей, поменявших свои места из-за опоздания одного зрителя.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест

Формат входных данных:
Входной файл INPUT.TXT состоит из трех строк. В первой строке содержится целое число N ( 1 <= N <= 30000) - количество мест в зале.
Вторая строка содержит последовательность из N целых чисел, разделенных пробелами, где первое число определяет номер места в билете у зрителя, который занял место с номером 1, второе - номер места в билете у зрителя, который занял место с номером 2, и так далее. Если место было свободно, то соответствующее число рано 0.
В третьей строке содержится одно число - номер места в билете у опоздавшего зрителя, который в антракте решил пересесть на свое место.

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число - количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.

Пример файлов входных и выходных данных:

INPUT.TXT                 OUTPUT.TXT
10                        3
0 2 5 3 4 0 0 0 0 0  
4

Задача 5. "Последовательность чисел" (28 баллов)

Рассмотрим бесконечную в обе стороны последовательность целых чисел F_i, в которой для любого целого i элемент F_i+2 вычисляется с использованием следующего условия Фибоначчи: F_i+2 = F_i+1+F_i. Пусть заданы два различных члена этой последовательности - F_i и F_j с соответствующми номерами i и j, а также некоторое целое число n. Необходимо восстановить элемент этой последовательности F_n, соответствующий номеру n.

Требуется написать программу, которая по заданным числам i, F_i, j, F_j, n вычисляет искомый элемент F_n описанной выше последовательности.

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест
Формат входных данных:
Входной файл INPUT.TXT содержит в одной строке разделенные пробелом следующие числа: i, F_i, j, F_j, n. Для этих чисел справедливы следующие ограничения:
-1000<= i, j, n <=1000;
-2000000000 <F_k<=2000000000 для всех k, удовлетворяющих условию min(i,j,n) <= k <= max(i,j,n).

Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать искомое число F_n

Пример файлов входных н выходных данных:

INPUT.TXT        OUTPUT.TXT
3 5 -1 4 5       12