Олимпиада по программированию.
Осень 1998. Заочный тур.
1. Сейф Карбофоса (10 секунд на тест).
В игре "Братья Пилоты" для выхода из комнаты Карбофоса
необходимо открыть сейф странной конструкции. На дверце сейфа
квадратом 4x4 расположены шестнадцать ручек, которые могут
находиться только в горизонтальном и вертикальном положении. При
повороте ручки на 90 градусов одновременно с ней поворачиваются
ручки, расположенные в той же самой горизонтали и вертикали, что и
поворачиваемая ручка. Например, при повороте ручки во 2 ряду 3
столбце получим следующий результат:
||-- |||-
|--| -||-
---| --||
|||- ||--
Для того чтобы открыть сейф, нужно чтобы все ручки приняли
горизонтальное положение.
Входной файл INPUT.TXT содержит в первой строке число N
(1<=N<=20) - количество наборов данных, далее следует N наборов
(начальных комбинаций), разделенных пустой строкой, каждый набор
представляет собой 4 строки по 4 символа | или - (начальное
состояние ручек).
В выходной файл OUTPUT.TXT для каждого набора, если сейф можно
открыть, вывести YES и через пробел минимальное число ручек,
поворачиваваемых для открытия сейфа, или NO в противном случае.
Пример входного файла: Пример выходного файла:
2 YES 1
--|- YES 6
||||
--|-
--|-
--||
----
----
----
2. Китайская грамота (10 секунд на тест).
Многие языки (китайский, японский и даже русский) содержат
большое число букв в алфавите, для которых нет прямых соответствий
в латинском алфавите. При передаче электронных писем может быть
потеряна или искажена любая информация с кодами вне диапазона
32-127 (пробел, цифры, латинский алфавит, пунктуация, а также
символы CR и LF). Тексты, содержащие другие символы, должны
кодироваться (UUencode, BASE64 или др. способом) при передаче и
декодироваться при получении. Для облегчения работы с короткими
текстами, а также при работе с компьютерами, на которых не
установлены необходимые шрифты, можно использовать мнемоническую
кодировку, заменяя буквы или сочетания букв похожими по
произношению сочетаниями латинских букв. Для человека процесс
кодирования-декодирования достаточно легок.
Требуется написать программу, декодирующую текст письма, чтобы
его можно было распечатать или вставить в документ.
Входной файл INPUT.TXT содержит в первой строке число N
(1<=N<=250) - количество кодов, далее следует N строк следующего
вида: я ya (исх.код пробел рез.код). Исходный код и результирующий
код содержат от 1 до 4 символов без пробелов. Для результирующего
кода используются только буквы латинского алфавита a-z, регистр не
имеет значения. Далее идет текст письма: от 1 до 10 строк не более
80 символов в строке.
Выходной файл OUTPUT.TXT должен содержать декодированный текст
письма. Все знаки препинания (символы, не являющиеся буквами
A-Za-z) должны сохраниться. Если слово можно интерпретировать
разными способами, выбирается интерпретация, содержащая наименьшее
количество кодов. Например: если заданы коды (бу bu, р r, я ya, й
y, а а) burya можно интерпретировать как буря (3 кода) и бурйа (4
кода). Выбирается первая интерпретация. Если две интерпретации
имеют одинаковое число кодов, то выбирается комбинация, коды
которой стоят раньше в списке кодов.
Пример входного файла: Пример выходного файла:
8 мама мыла раму. лара рыла яму.
м m
a a
ы iq
л L
р r
у u
я ya
й y
Mama miqla ramu. Lara riqla yamu.
3. Выжимание воды (5 секунд на тест).
Для уменьшения количества "воды" в текстах можно либо научиться
писать кратко, либо просто сжимать получивщиеся тексты.
Естественно, для программиста легче использовать второй путь.
Напишите программу, сжимающую текст. Словом будем называть
последовательность прописных и строчных латинских букв (до 50
символов). Регистр букв игнорируется.
x-ray состоит из 2 слов X и RAY
Mary's состоит из 2 слов MARY и S
It's words состоит из 3 слов IT, S и WORDS
Повторяющееся слово будем заменять символом # и номером его
последнего вхождения, отсчитываемым от текущего слова. Если слово
достаточно коротко (при замене не происходит уменьшения текста), то
замену не делаем. Знаки препинания, разделение на строки, остается
как в исходном тексте.
Входной файл INPUT.TXT содержит текст для сжатия (от 1 до 50
строк, не более 80 символов в строке, не более 200 слов в тексте).
Выходной файл OUTPUT.TXT должен содержать получившийся сжатый
текст.
Пример входного файла:
Dear Sally,
Please, please do it--it would please
Mary very, very much. And Mary would
do everything in Mary's power to make
it pay off for you.
-- Thank you very much--
Пример выходного файла:
Dear Sally,
Please, #1 do it--it would #5
Mary very, #1 much. And #5 #8
do everything in #5's power to make
it pay off for you.
-- Thank #2 #20 #20--