Задачи второго тура
III-го этапа Всероссийской олимпиады школьников по информатике
(10-11 класс, 2001-2002 учебный год, Пермская область)

 

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

Входной файл: INPUT.TXT          Выходной файл: OUTPUT.TXT

Ограничение по времени: 15 секунд (на компьютере с процессором Pentium-100).

 

1) «Новобранцы». (Идея — материалы методической комиссии 2001-2002 г., составитель — Брызгалов Е.В., оппонент — Деменев А.Г.) 10 баллов.

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

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

Формат входных данных:
В первой строке содержится натуральное число N (N <= 30000) — количество cолдат в шеренге.
Вторая строка содержит последовательность из N символов, каждый из которых может быть либо символом «<», либо символом «>». («<» обозначает солдата, повернувшегося налево, «>» — направо).

Формат выходных данных:
Либо одно число — количество развернувшихся пар, либо слово NO, если процесс бесконечен.

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

6
>><<><

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

7

 

2) «T-система». (Автор-составитель — Еремин Е.А., оппонент — Шестаков А.П.) 15 баллов.

Система счисления, принятая у трехпалых обитателей планеты TOI (условимся называть ее T-системой и помечать записанные в ней числа индексом T), устроена по следующим правилам.

Все числа записываются с помощью трех цифр, в качестве которых используются заглавные латинские буквы T, O и I, причем T обозначает -1, O - ноль, а I соответствует +1. Тогда любое число представляется в виде суммы произведений таких цифр на степени числа 3, например:

810 = 9 - 1 = I * 32 + O * 31 + T * 30 = IOTT

Требуется написать программу, которая переведет произвольное целое десятичное число в T-систему, если известно, что модуль максимального используемого на планете числа принят равным 3000010.

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

Формат входных данных:
Одна строка, содержащая запись числа.

Формат выходных данных:
Одна строка, содержащая результат перевода в T-систему.

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

8

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

IOT

 

3) «Звезда». (Составитель — Брызгалов Е.В., автор-оппонент — Деменев А.Г.) 20 баллов.

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

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

Примечания:

Формат входных данных:
В первых 5 строках содержится по два натуральных числа — координаты вершин звезды. В шестой строке расположено число M (1 <= M <= 10000) — количество помеченных узлов. Далее следует M строк, каждая из которых содержит 2 натуральных числа — координаты помеченного узла.

Формат выходных данных:
Одно число — количество помеченных узлов внутри звезды.

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

3 6
2 1
1 5
4 5
1 2
3
1 1
4 3
2 4

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

1

 

4) «Забытые пробелы». (Автор-составитель — Брызгалов Е.В., оппонент — Гладков В.П.) 25 баллов.

Мальчик написал несколько натуральных чисел так, чтобы они образовывали возрастающую последовательность. Она ему так понравилась, что он решил послать её по электронной почте своему брату-программисту в далекую западную страну. К сожалению, клавиша «пробел» на клавиатуре стала «западать» и все числа последовательности оказались записанными подряд, без символов-разделителей. Увы, но мальчик заметил это слишком поздно…

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

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

Формат входных данных:
Одна строка (не более 80 символов), состоящая из цифр.

Формат выходных данных:
Одна строка, полученная из исходной добавлением нескольких пробелов и удовлетворяющая условиям задачи.

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

57198

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

5 7 198 
или 
5 71 98

 

5) «Охотник». (Автор-составитель — Брызгалов Е.В., оппонент — Гладков В.П.) 30 баллов.

На шахматной доске стоит конь и N (1 <= N <= 11) пешек.

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

Примечание: любое поле на шахматной доске обозначается парой символов — латинской буквой от ‘a’ до ‘h’ (обозначает столбец доски — вертикаль) и арабской цифрой от ‘1’ до ‘8’ (обозначает строку доски — горизонталь).

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

Формат входных данных:
Первая строка — поле, на котором стоит конь.
Вторая строка — количество пешек — N.
Далее следует N строк, в каждой из которых содержится поле, на котором стоит одна из пешек.

Формат выходных данных:
Одна строка, содержащая минимальное число ходов.

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

c5
2
b2
b3

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

4

 

© Пермский областной Оргкомитет олимпиад школьников по информатике, 2001

 


Рейтинг ресурсов УралWeb

Сайт создан в системе uCoz