Сетка — это поле, разбитое на квадраты. На ней построена пятиконечная звезда, все пять концов, которой расположены в узлах сетки. Затем были помечены M произвольных узлов сетки.
Технические требования:
Входной файл: 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, например:
Требуется написать программу, которая переведет произвольное целое десятичное число в 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