Южно-Уральский командный
чемпионат по программированию 2001
Во всех задачах ввод данных производится из
файла INPUT.TXT, а вывод результатов - в файл OUTPUT.TXT. Формат входного файла
соответствует спецификации, дополнительные проверки не нужны.
Строка – это последовательность из 0 или
более символов, заканчивающаяся символом перехода на новую строку (т.е.
последним символом входного файла будет символ перехода на новую строку).
Время теста указано для тестирующего
компьютера жюри Pentium-166.
1. БАЗАР КОЛЛЕКЦИОНЕРОВ В ГОРОДЕ ПАЛАПУТРА (5 сек на тест)
Профессор
Селезнев хочет приобрести для Московского зоопарка невидимых воздушных рыбок.
Рыбки распределены по нескольким аквариумам, расставленным на M
полках. На каждой полке расположено по N
аквариумов таким образом, что образуется N
вертикальных рядов. Отличить пустой аквариум от аквариума с рыбками по внешнему
виду нельзя и вполне возможно, что некоторые из аквариумов пустые. Продавец не
знает, сколько рыбок в каждом аквариуме, но у него записано, сколько рыбок в
сумме на каждой полке и в каждом вертикальном ряду. Помогите профессору
Селезневу найти какой-нибудь аквариум с рыбками, используя эту информацию.
Во входном файле в первой строке содержатся два целых числа M (1£M£5)
и N (1£N£5)
через один пробел – число полок и число рядов. Во второй строке содержатся M чисел через один пробел – суммарное число
рыбок в аквариумах на каждой полке. В третьей строке содержится N
чисел через один пробел – суммарное число рыбок в аквариумах каждого
вертикального ряда. (Сумма чисел во второй строке всегда равна сумме чисел в
третьей строке входного файла.)
В выходной файл вывести два целых числа через один пробел – номер
полки и номер вертикального ряда, в котором находится аквариум, в котором есть,
по крайней мере, одна рыбка. Номера полок отсчитываются с 1, начиная с верхней
полки. Номера рядов - с 1, начиная слева. Если определить номер непустого
аквариума невозможно, то вывести "0 0" (два нуля, кавычки не
выводить).
INPUT.TXT для примера 1:
2 2
2 1
1 2
OUTPUT.TXT для примера 1:
1 2
INPUT.TXT для примера 2:
2 2
2 2
2 2
OUTPUT.TXT для примера 2:
0 0
2. ЗАГАДКА СНЕЖНОЙ КОРОЛЕВЫ (10 сек на тест)
Кусочки льда, из которых Кай складывал слово "вечность",
были осколками правильного n-угольника.
Правильный n-угольник (3£n£10)
был разбит на треугольные осколки следующим способом. Внутри n-угольника
выбирается некоторая точка, в которую наносится удар. Линии раскола являются
прямыми и проходят от этой точки ко всем
вершинам n-угольника и к нескольким (0 или
более) точкам на сторонах n-угольника.
Определите по размерам осколков количество углов n-угольника.
Во входном файле в первой строке содержится целое число M (n£M£20)
– количество осколков. В следующих M
строках содержатся по три вещественных числа – длины сторон треугольных
осколков. Длины сторон округлены до 3 знаков после запятой (все длины сторон не
превосходят 15 и не меньше 1).
В выходной файл вывести число n
– количество углов правильного n-угольника.
Если программа не сможет определить количество углов, то вывести 0 (ноль).
Пример INPUT.TXT:
5
6.000 3.606 3.606
3.606 3.000 3.162
5.000 3.000 3.162
5.000 6.000 5.000
5.000 6.000 3.606
OUTPUT.TXT для примера:
4
3. УЖАСНЫЕ БОЛОТА ПЛАНЕТЫ ТОПЛЕР (5 сек на тест)
Планета Топлер "прославилась" своими болотами. Многолетние
наблюдения за жизнедеятельностью болот выявили следующие закономерности. Болото
можно разбить на небольшие квадратные участки-клетки. Каждые 4 секунды в каждой
клетке возникает большой пузырь-площадка, который постепенно в течении 3 секунд
уменьшается, пока не исчезнет совсем. В течении 1 секунды клетка остается
пустой, затем снова появляется пузырь, и цикл повторяется (возможно такое
странное поведение пузырей объясняется обратным направлением вектора времени на
планете Топлер). В течении первых 2,5 секунд существования пузырь может
выдержать довольно большой вес (например, вес робота).
Для исследований планеты был изготовлен специальный прыгающий робот
(на двух ножках и с длинным носом для равновесия). Робот может совершать прыжки
в четыре стороны на соседние пузыри. Будем считать, что подготовка к прыжку
занимает полсекунды, и на приземление после прыжка тратится полсекунды, а сам
прыжок совершается мгновенно (робот не должен прыгать в клетку, которая в
момент прыжка пуста, а также в клетку с пузырем, которому осталось существовать
1 секунду, если мы не хотим утопить робота в болоте). Для управления роботом
используются команды: N – прыжок на север, S – на юг, W – на запад, E – на
восток и D – остановка на 1 секунду.
Имеется снимок болота размером NxM клеток. Требуется составить программу для
перехода робота через болото из юго-западного угла в северо-восточный.
Во входном файле в первой строке содержатся два целых числа N (1<N£50)
и M (1<M£50)
через один пробел – размеры болота в клетках. Далее идет N
строк по M целых чисел через один пробел в
каждой строке – состояние пузырей в клетках болота (клетки перечисляются с
запада на восток и с севера на юг). Число 0 означает, что клетка в данный
момент пуста и останется пустой в течении секунды, число от 1 до 3 означает
оставшееся время существования пузыря в секундах (или его размер). Размер
пузыря в юго-западном углу болота равен 3 (мы же не хотим утопить робота в
первую же секунду!).
В выходной файл вывести программу управления роботом, которая
позволяет достичь северо-восточного угла за минимальное
время. Последовательность команд должна быть выведена как одна строка без
пробелов. Если возможно несколько вариантов, то вывести любой из них. Если
переход невозможен, вывести слово "IMPOSSIBLE" (кавычки не выводить).
Пример INPUT.TXT:
3 4
3 2 3 3
0 0 1 2
3 3 1 2
OUTPUT.TXT для примера:
ENEEN
4. «ВЫВЕРНУТАЯ» ПАМЯТЬ (10
сек на тест)
После аварии в гиперпространственном прыжке звездолет
"ФАЭТОН" оказался зеркально отраженным – левое поменялось с правым.
Сердце у всех астронавтов стало справа, а название корабля превратилось в
"НОТЄАФ".
Также «вывернутой» оказалась и память компьютера, управляющего движением
корабля. Для выполнения следующего гиперпространственного прыжка нужно исправить
двоичное представление программы в памяти компьютера. Для этого необходимо
поменять местами биты в 16-битных словах (выполнить зеркальное отражение): 0-й
бит должен стать 15-м, 1 – 14, 2 – 13 и т.д. Пример отражения:
0110001011101101
®
1011011101000110
Во входном файле в первой строке содержится целое число N (0<N£32768)
– размер программы в 16-битных словах. Далее следует N
строк, в каждой строке содержится одно число от 0 до 65535 – десятичное
представление слов программы.
В выходной файл вывести N строк,
по одному числу в строке – десятичное представление слов программы после
зеркального отражения.
Пример INPUT.TXT:
3
1
0
32767
OUTPUT.TXT для примера:
32768
0
65534
5. А И Б СИДЕЛИ НА ТРУБЕ (5 сек на тест)
В фильме "Отроки во Вселенной" юные космонавты выводили
из строя роботов с помощью головоломки про А и Б, сидевших на трубе. Помогите
бедным роботам и напишите программу для решения подобных головоломок.
Входной файл представляет собой текст из трех или более строк.
Длина строк текста не превышает 200 символов. Используются только прописные
русские буквы, кроме Ё (буквы с кодами с 128 по 159), пробелы и знаки
препинания, в некоторых словах (КТО–ТО) и именах (ШАЛТАЙ–БОЛТАЙ) употребляется
символ – (минус). В первой строке текста перечисляются имена
нескольких (одного или более) персонажей, разделенных пробелами и/или запятыми;
имена персонажей не повторяются. Во второй строке описывается местонахождение
этих персонажей. В последующих строках (кроме последней) описывается их
исчезновение с места событий, причем имя персонажа всегда стоит первым в
строке. В последней строке задается вопрос о персонажах, которые остались на
первоначальном месте.
В выходной файл вывести имена оставшихся персонажей, разделяя их
запятой и пробелом, в порядке, в котором они перечислялись в первой строке головоломки;
в конце списка вывести точку. Если никого из персонажей не осталось, то вывести
только точку.
Пример INPUT.TXT:
ИВАНОВ, ПЕТРОВ И СИДОРОВ
СИДЕЛИ НА ДИВАНЕ.
ИВАНОВ РАЗБЕЖАЛСЯ
И ВЫПРЫГНУЛ В ОКНО.
КТО ОСТАЛСЯ СИДЕТЬ НА ДИВАНЕ?
OUTPUT.TXT для примера:
ПЕТРОВ, СИДОРОВ.
6. КОСМИЧЕСКОЕ ПРИКЛЮЧЕНИЕ (5 сек на тест)
После спасения от нападения сариэнов Роджер Вилко оказывается в
космическом порту на планете Керона. Продав скиммер, Роджер получил 30
буказоидов, но этих денег было недостаточно на покупку звездолета. Зайдя в бар,
он увидел, как двое инопланетян играют на деньги в игру “шашки в ряд”.
Правила
игры оказались довольно простые. У каждого игрока по 32 шашки белого или
черного цвета. Игроки ставят по очереди на доску размером 8x8 по две шашки своего цвета, стремясь
выстроить горизонтальные или вертикальные ряды как можно большей длины. Самой
сложный этап игры – подсчет очков, начинается после того, как доска заполнена шашками. Ряд из двух
одноцветных шашек дает их владельцу 22=4 очка, из трех 32=9
очков, из четырех 42=16 очков и так далее. Шашка, стоящая
одновременно в двух рядах, учитывается только один раз. Одиночные шашки не
учитываются. При разных подходах к подсчету можно получить различное количество
очков. Например, группу из 6 черных шашек в левом нижнем углу доски можно
рассматривать как три вертикальных ряда по две шашки в каждом, что дает
4+4+4=12 очков. Если эту группу рассматривать как два горизонтальных ряда по
три шашки в каждом, то получится 9+9=18 очков. Как видно, разница существенная.
Победителем игры становится обладатель большего количества очков, а побежденный
платит ему столько буказоидов, сколько составляет разница очков.
Вскоре Роджер Вилко, используя свой недюжинный ум и кнопку Save, выиграл недостающую
сумму на покупку звездолета и покинул пустынную Керону. Вам же предстоит
написать программу для подсчета очков.
Во входном файле содержится 8 строк по 8 символов – окончательная
позиция в игре. Символом X
(икс) обозначаются черные шашки, а O – белые шашки.
В выходной файл вывести два числа через пробел: наибольшее
количество очков для игрока, играющего черными шашками, и наибольшее
количество очков для игрока, играющего белыми шашками.
Пример INPUT.TXT:
OOOOOXXX
OXOXOOXX
OXOXOOOO
XOOXXOOX
XOOXXOOX
OOOXXXXX
XXXOXOXO
XXXOXOXO
OUTPUT.TXT для примера:
107 104
7. ROMULAN SPELLING (5 сек на тест)
Year 2000 ACM
(after computing machinery). The Romula is a lost human colony near b Canopguk. The Romulans use a
language that can be approximated with the English alphabet and normal
punctuation marks. Their spelling rules are even stranger than English,
however. In particular, they have a rule that states:
G before P except
after E or when pronounced X as in npgukbor or wpguk.
Operationally, you
can detect the X pronounciation by the string PGUK appearing in the word. Also,
the Romulan rules for capitalization are different from ours, so capital
letters can appear anywhere in a word.
Input and Output
Given a file
containing lines of Romulan text, you are to output the text with spelling
corrected according to the G before P except after E rule given above. No input
line will contain more than 70 characters including spaces.
For example, the
input file corresponding to the romulan translation of the quote:
"I received
the wierd piece of pie from my neighbor sam who in turn recieved the weird
peice of pei from his nieghbor harry," might well be ...
Sample INPUT.TXT
I rpEpgvpd tKp
wgprd tgpEp of tgp from my npguKbor sam wKo gn
turn rpEgpvpd
tKp wpgrd tpgEp of tpg from Kgs ngpuKbor Karry,
Sample OUTPUT.TXT
I rpEpgvpd tKp
wgprd tgpEp of tgp from my npguKbor sam wKo gn
turn rpEpgvpd
tKp wgprd tgpEp of tgp from Kgs npguKbor Karry,
