Тверская областная олимпиада по информатике 2002 года

Муниципальное общеобразовательное учреждение

средняя общеобразовательная школа №4

Территориальный ресурсный центр

Тверская область, г. Нелидово, ул. Карбышева 14А

Областная олимпиада по информатике 2002 года

Задача №1. «Новобранцы» (25 баллов)

На первом построении вновь призванные в армию солдаты построились в шеренгу. После небольшого объяснения им правил выполнения строевых команд последовала команда «налево». В результате исполнения этой команды некоторые солдаты повернулись налево, а некоторые — направо. Солдаты, которые оказались лицом к лицу со своим соседом, сразу поняли, что совершили ошибку. Чтобы ее исправить, каждый из них опять быстро повернулся на 180 градусов. Если названная ситуация затем опять повторялась, то есть в каких-то парах солдаты оказывались лицом друг к другу, то такие солдаты снова поворачивались на 180 градусов. Эта процедура повторялась до тех пор, пока в шеренге была хотя бы пара солдат, стоящих лицом друг к другу.

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

Технические требования:

Входной файл: INPZli.TXT, i - номер теста. Выходной файл: OUTZli.TXT, i - номер теста. Вывод результата должен осуществляться также на экран монитора. Ограничение по времени тестирования: 30 секунд на один тест.

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

Входной файл INPZli.TXT состоит из двух строк. В первой строке этого файла записано целое число N (l<=N<=30000) — количество солдат в шеренге. Вторая строка содержит последовательность из N символов, каждый из которых может быть либо символом <, либо символом > (символ < обозначает солдата, который повернулся налево, символ > — солдата, который повернулся направо).

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

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

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

>><<><

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

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

Расположение солдат	Количество пар, которые должны развернуться	Комментарий
>><<><	2	Входные данные
><><<>	2	После первого разворота
<><><>	2	После второго разворота
<<><>>	1	После третьего разворота
<<<>>>	Всего - 7

Задача №2. «Театр» (20 баллов)

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

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

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

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

Входной файл: INPZ2i.TXT, i - номер теста. Выходной файл: OUTZ2i.TXT, i - номер теста. Вывод результата должен осуществляться также на экран монитора. Ограничение по времени тестирования: 30 секунд на один тест. Формат входных данных:

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

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

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

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

Ввод Вывод

10 3

0253400000

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

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

Технические требования:

Входной файл: INPZ3i.TXT, i - номер теста. Выходной файл: OUTZ3i.TXT, i - номер теста. Вывод результата должен осуществляться также на экран монитора. Ограничение по времени тестирования: 30 секунд на один тест.

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

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

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

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

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

Ввод Вывод

8 4 0 1

13 29 37 5 3 3

8 1

2 0

8 4

1 1 1 1 2 Нет решения

Задача №4. «Пчела» (30 баллов)

В улье, изображенном на рисунке, в поисках нужной соты ползает пчела. Как видно из рисунка, соты представляют собой шестиугольники, и пчела может переползать из одной соты в соседнюю с ней вдоль заданных осей координат X,Y или Z. После того, как пчела оказалась в нужной ей соте, она должна возвратиться в исходную соту по пути, содержащем по возможности наименьшее количество промежуточных сот. Необходимо этот путь определить. Путь пчелы задается в виде последовательности пар следующего вида: сначала записывается буква (X,Y или Z), определяющая, на сколько сот пчела перемещается в этом направлении.

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

Технические требования: Входной файл: INPZ4i.TXT, i - номер теста. Выходной файл: OUTZ4i.TXT, i - номер теста. Вывод результата должен осуществляться также на экран монитора. Ограничение по времени тестирования: 30 секунд на один тест.

Формат входных данных: Входной файл INPZ4i.TXT состоит из последовательности строк. В первой строке этого файла записано целое число N (l<=N<=32000) — количество звеньев пути пчелы из начальной соты в конечную. Последующие N строк содержат описания звеньев пути пчелы из начальной соты в конечную в порядке ее перемещения. В каждой строке сначала идет буква (X,Y или Z), определяющая направление движения, а затем - целое число К, задающее, на сколько сот пчела перемещается в этом направлении. Буква и число разделяются ровно одним пробелом.