Личное
первенство университета по программированию
Во всех задачах ввод данных
производится из файла INPUT.TXT, а вывод результатов – в файл OUTPUT.TXT. Формат
входного файла соответствует спецификации, дополнительные проверки не нужны. Все
строки, в том числе последняя, оканчиваются символом перехода на новую строку.
Время теста указано для процессора Celeron-600.
1. CIV
(5 сек
на тест)
Вам необходимо разработать один из модулей
стратегической игры CIV, который находит оптимальный путь для юнита
(unit) между двумя точками на карте. Карта мира разделена
на квадратные клетки-участки разного типа. Для прохода по ровной местности юнит
тратит 1 единицу движения. При движении по лесу или холмам затраты составляют 2
единицы движения. При движении по горам или джунглям тратится 3 единицы
движения. Имеются также клетки (вода), движение по которым
запрещено.
Кроме того, имеется сеть дорог двух видов. Если
клетки карты соединены обычной дорогой, то
юнит на переход из одной клетки в другую затрачивает 1/3 единицы
движения. Если клетки соединены железной дорогой, то на переход не тратится ни
одной единицы движения. Если клетки не соединены дорогой, то затраты на переход
определяются типом клетки, в которую осуществляется переход (тип покидаемой
клетки на стоимость перехода не влияет).
В зависимости от типа, юнит может потратить во время
каждого хода одну (пешеход), две (всадник) или три (танк) единицы движения. В
конце хода юнит может переходить из одной клетки в другую, даже если количество
оставшихся единиц движения меньше требуемого для перехода. При этом он теряет
все оставшиеся единицы движения, но на движении при следующем ходе это не
сказывается. Таким образом, при движении по горам без дорог юнит-пешеход и
юнит-танк имеют одинаковую скорость – 1 клетка за ход.
Юнит может ходить по горизонтали, по вертикали и по
диагонали в соседние клетки.
Напишите программу, которая рассчитает минимальный
(по количеству затраченных единиц движения) путь для юнита на заданной
карте.
Во входном
файле в первой строке содержится семь целых чисел, разделенных пробелами –
размеры карты W
и
H, координаты
начальной клетки X1,
Y1, координаты
конечной клетки X2,Y2 и
количество единиц движения M, которое
юнит может потратить на каждом ходе (1<W<=100,
1<H<=100, 1<=X1<=W,
1<=X2<=W, 1<=Y1<=H,
1<=Y2<=H, 1<=M<=3).
Далее следует H строк,
содержащих по 2*W символов –
карта мира. Каждая пара символов содержит информацию об одной клетке.
Запрещенные для движения клетки обозначаются символами ** (две звездочки). Для
остальных клеток первый символ (‘1’, ‘2’ или ‘3’) показывает затраты при
движении по данной местности, а второй символ показывает наличие дорог. Символ
‘.’ (точка) означает отсутствие дорог, символ ‘-‘ (минус) означает наличие
обычной дороги, а символ ‘=’ (равно) – железной дороги. Если в соседних клетках
есть отметка ‘=’, то эти две клетки соединены железной дорогой. Если в одной
клетке есть отметка ‘-‘, а в соседней клетке отметка ‘-‘ или ‘=’, то эти две
клетки соединены обычной дорогой. В остальных случаях дороги между клетками нет.
Координаты (1,1) соответствуют левому верхнему углу карты, а координаты
(W,H) – правому
нижнему.
В выходной
файл дробь вида P/3, если от
начальной до конечной клетки можно пройти, затратив только единиц движения. Если от начальной до
конечной клетки дойти невозможно, то в файл вывести одну строку с сообщением
IMPOSSIBLE.
Пример INPUT.TXT:
5 3
1 1 5 3 2
1.2-3-2-3-
1.**3.**2-
1.1.1=2=1=
OUTPUT.TXT для примера:
9/3
2. Стрелки
(5 сек
на тест)
Боб решил вырезать
несколько стрелок вида “>>->” из узкой полоски
бумаги, на котором были напечатаны символы ‘–‘ (минус), ‘>’ (больше) и ‘<’
(меньше). Искажения в виде стрелки недопустимы, например, “древко” стрелки
должно состоять точно из одного символа ‘–‘. Вырезанные стрелки должны быть
цельными, так как Боб не хочет склеивать стрелки из отдельных кусочков. Также
кусочки бумаги нельзя сгибать, но можно поворачивать после разрезания для
получения стрелки указанного вида.
Во входном файле
содержится строка длиной от 1 до 250 символов, состоящая только из символов ‘–‘,
‘>’, ‘<’. Это содержимое полоски бумаги, которая есть у
Боба.
В выходной файл вывести
одно целое число – максимальное количество стрелок вида “>>->”, которое Боб сможет
вырезать из заданной полоски.
Пример INPUT.TXT:
<->>-->>>->>->>->>>->>->>-
OUTPUT.TXT для примера:
3
3. Кубик Ьубика
(5 сек
на тест)
На последнем чемпионате
мира по сборке кубика Рубика (www.rubikchamps.com) был установлен новый
мировой рекорд. Программист С. собрал кубик всего за 20 секунд. Таких
потрясающих результатов ему удалось добиться при помощи собственной программы,
которая для любого начального состояния кубика выдавала оптимальную
последовательность действий для сборки кубика. Конечно, он использовал эту
программу только для подготовки к соревнованиям, так как она работала довольно
долго.
В этой задаче вы должны
написать аналогичную программу для кубика Ьубика, который устроен гораздо проще
кубика Рубика. Кубик Ьубика состоит из восьми единичных кубиков, соединенных
центральным механизмом в куб размером 2x2x2. Любую половину кубика
Ьубика (верхнюю, нижнюю, левую, правую, переднюю или заднюю) можно поворачивать
относительно другой на угол, кратный 90 градусов. Четыре единичных кубика в
головоломке целиком покрашены в черный цвет, а четыре других – целиком в белый
цвет. Кубик считается собранным, если его можно разделить плоскостью на две
части (по 4 кубика), каждая из которых окрашена в свой
цвет.
Из всех возможных
манипуляций с кубиком удобнее всего использовать следующие
шесть:
·
CW – поворот всего кубика
по часовой стрелке;
·
CCW – поворот всего кубика
против часовой стрелки;
·
LU – поворот левой половины
кубика вверх;
·
LD – поворот левой половины
кубика вниз;
·
RU – поворот правой
половины кубика вверх;
·
RD – поворот правой
половины кубика вниз.
При повороте RU кубик 2 переходит на место кубика 4, кубик 4 – на место кубика 8, 8 – на 6, а 6 – на 2.
Во входном файле содержится одна строка из восьми символов B и W. Символ B означает черный цвет, а символ W – белый; i-ый символ строки соответствует цвету i-ого кубика (нумерация кубиков показана на рисунке). Строка содержит 4 символа B и 4 символа W.
В выходной файл в первой
строке вывести целое число N – минимальное количество
действий над кубиком, приводящее к решению головоломки. Далее должны быть
выведены N строк с этими
действиями, каждое действие на отдельной строке. Любой минимальный вариант
решения может быть выведен.
Пример INPUT.TXT:
BWWBBWWB
OUTPUT.TXT для примера:
2
RU
RU
4. Счастливый билет
(5 сек
на тест)
Номер билета состоит из 6
цифр. Эти цифры можно использовать для головоломки, которую можно решать по
дороге. Требуется расставить между цифрами номера (не изменяя их порядка) знаки
4 арифметических действий (+, –, * и /) и скобки таким образом, чтобы получилось
правильное арифметическое выражение, равное заданному целому числу. Деление
разрешается использовать только в случае, если деление производится без остатка.
Унарный минус, возведение в степень и другие операции использовать запрещено.
Используя один и тот же набор цифр можно получать разные числа. Обычно пытаются
получать последовательно все целые числа, начиная с нуля. Например, из номера
111112 можно получить число 0 как (11-11)*12, 1 как 1+(11-11)*2, 2 как
1*(1+1-(1/1))+2 и т.д. Определим уровень ”счастья”, заложенный в номере билета,
как наименьшее неотрицательное целое число, которое нельзя получить, используя
цифры номера билета. Таким образом, чем больше уровень “счастья”, тем дольше
можно решать головоломку.
Во входном файле
содержится один номер из 6 цифр (от 000000 до 999999).
В выходной файл вывести
одно целое число – наименьшее неотрицательное целое число, которое нельзя
получить, используя цифры заданного номера.
Пример INPUT.TXT:
111112
OUTPUT.TXT для примера:
29
5. SPAM
(5 сек
на тест)
Объем электронной
рекламной почты (spam) уже превысил в начале
этого года 50% от общего объема почтовых сообщений и быстро растет. Прогнозируют
даже, что такой экспоненциальный рост объемов спама может серьезно повлиять на
пропускную способность сетей. Наиболее эффективный способ снижения этого трафика
– законодательный, но пока соответствующие законы приняты не во всех странах, и
приходится использовать специальные программы для сортировки корреспонденции.
Спамеры используют различные ухищрения для обхода этих программ. Например,
посылают письмо как Web-страницу, где каждый
символ обрамлен в теги со случайно сгенерированным
содержимым.
Напишите программу,
выявляющую письма с текстом, который является результатом случайной генерации.
Будем использовать следующие признаки:
·
Письмо содержит слово, в
котором есть пять согласных подряд.
·
Письмо содержит слово, в
котором есть пять гласных подряд.
·
В письме в словах из пяти
или более букв есть в сумме три или более комбинации букв, которые недопустимы в
английском языке (например, QE, ZC, YY).
Примечания: Словом будем называть непрерывную
последовательность прописных и строчных латинских букв. Регистр букв в этой
задаче не важен. Гласными являются буквы A,E,I,O,U,Y. Слова из 4 или менее
букв могут быть сокращениями, в которых появление недопустимых комбинаций
возможно. В слове YYYYY содержится четыре недопустимых комбинации букв
YY.
Во входном файле в первой
строке содержится одно целое число K (0<=K<=100) – количество
недопустимых комбинаций букв. Далее следует K строк, содержащих по две
латинских буквы – недопустимые комбинации. Далее следует одна или более строк
длиной от 1 от 250 символов. Каждая строка содержит текст одного
письма.
В выходной файл для
каждого письма вывести строку с сообщением SPAM, если обнаружен один из
признаков случайной генерации, или OK в противном
случае.
Пример INPUT.TXT:
2
qE
YY
QeQeQe
S<QE>A</QE>L<QE>E</QE>S!!!
You
win US$5,000,000! Send your CC info
From:
QSWRSD@yahoo.com
ABYYY
ABBYY
OUTPUT.TXT для примера:
SPAM
OK
OK
SPAM
SPAM
6.
Soundex Indexing (5
сек на тест)
The Soundex Index System
was developed so that similar sounding names, or names with similar spelling
could be encoded for easy retrieval. It has been used by the U.S. Bureau of the
Census, and some States use it to help encode your driver's license number. Your
task is to read a sequence of names, one at a time and one per line, compute the
corresponding soundex code, and write to the output file the name and its
soundex code (one line of output per name).
Names
will contain from 1 to 20 upper case, alphabetic characters (ASCII values 65
thru 90, inclusive). Names shorter than 20
characters will NOT be padded with blanks. Thus a name will consist of upper
case letters only.
A Soundex Code always
consists of a letter followed by three digits. Here are the rules for soundex
encoding:
1. The first letter of a
name appears as the first and only letter in the soundex code.
2. The letters A, E, I,
O, U, Y, W and H are never encoded, but do break successive code sequences (see
next rule).
3. All other letters are
encoded EXCEPT when they immediately follow a letter (including the first
letter) that would be encoded with the same code digit.
4. The soundex code guide
is:
Code |
Key Letters and
Equivalents |
1 |
B, P, F, V |
2 |
C, S, K, G, J, Q, X,
Z |
3 |
D, T |
4 |
L |
5 |
M, N |
6 |
R |
5. Trailing zeros are
appended to short codes so all names are encoded with a letter followed by three
digits.
6. Longer codes are
truncated after the third digit.
The input file contains a
list of names, one per line. Each name will not exceed 20 characters, and you
may assume that only upper case letters will be used. Your program should
continue to read names until the end of the file is detected.
The output written to the
file should consist of a column of names and a column of their corresponding
soundex codes. Write the headings ``NAME" and ``SOUNDEX CODE" in the first line
of the output file in columns 10 and 35, respectively. After
the heading line, the names and soundex codes should be written (one pair per
line) with the name starting in column 10 and the soundex code beginning in
column 35.
Пример INPUT.TXT:
LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK
OUTPUT.TXT для
примера:
NAME SOUNDEX CODE
LEE L000
KUHNE K500
EBELL E140
EBELSON E142
SCHAEFER S160
SCHAAK S200