7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2003

Подразделы

Другие разделы

Дата и время

26/04/2024 07:41:45

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи очного тура личного первенства университета 2003

1. CIV

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вам необходимо разработать один из модулей стратегической игры CIV, который находит оптимальный путь для юнита (unit) между двумя точками на карте. Карта мира разделена на квадратные клетки-участки разного типа. Для прохода по ровной местности юнит тратит 1 единицу движения. При движении по лесу или холмам затраты составляют 2 единицы движения. При движении по горам или джунглям тратится 3 единицы движения. Имеются также клетки (вода), движение по которым запрещено.
Кроме того, имеется сеть дорог двух видов. Если клетки карты соединены обычной дорогой, то юнит на переход из одной клетки в другую затрачивает 1/3 единицы движения. Если клетки соединены железной дорогой, то на переход не тратится ни одной единицы движения. Если клетки не соединены дорогой, то затраты на переход определяются типом клетки, в которую осуществляется переход (тип покидаемой клетки на стоимость перехода не влияет).
В зависимости от типа, юнит может потратить во время каждого хода одну (пешеход), две (всадник) или три (танк) единицы движения. В конце хода юнит может переходить из одной клетки в другую, даже если количество оставшихся единиц движения меньше требуемого для перехода. При этом он теряет все оставшиеся единицы движения, но на движении при следующем ходе это не сказывается. Таким образом, при движении по горам без дорог юнит-пешеход и юнит-танк имеют одинаковую скорость – 1 клетка за ход.
Юнит может ходить по горизонтали, по вертикали и по диагонали в соседние клетки.
Напишите программу, которая рассчитает минимальный (по количеству затраченных единиц движения) путь для юнита на заданной карте.
Ввод
Во входном файле в первой строке содержится семь целых чисел, разделенных пробелами – размеры карты W и H, координаты начальной клетки `X_1,\ Y_1`, координаты конечной клетки `X_2,\ Y_2` и количество единиц движения `M`, которое юнит может потратить на каждом ходе `(1\ <\ W\ ≤\ 100,\ 1\ <\ H\ ≤\ 100,\ 1\ ≤\ X_1\ ≤\ W,\ 1\ ≤\ X_2\ ≤\ W,\ 1\ ≤\ Y_1\ ≤\ H,\ 1\ ≤\ Y_2\ ≤\ H,\ 1\ ≤\ M\ ≤\ 3)`. Далее следует `H` строк, содержащих по `2*W` символов – карта мира. Каждая пара символов содержит информацию об одной клетке. Запрещенные для движения клетки обозначаются символами ** (две звездочки). Для остальных клеток первый символ ('1', '2' или '3') показывает затраты при движении по данной местности, а второй символ показывает наличие дорог. Символ '.' (точка) означает отсутствие дорог, символ '-' (минус) означает наличие обычной дороги, а символ '=' (равно) – железной дороги. Если в соседних клетках есть отметка '=', то эти две клетки соединены железной дорогой. Если в одной клетке есть отметка '-', а в соседней клетке отметка '-' или '=', то эти две клетки соединены обычной дорогой. В остальных случаях дороги между клетками нет. Координаты (1,1) соответствуют левому верхнему углу карты, а координаты `(W,\ H)` – правому нижнему.
Вывод
В выходной файл дробь вида `P/3`, если от начальной до конечной клетки можно пройти, затратив только `P/3` единиц движения. Если от начальной до конечной клетки дойти невозможно, то в файл вывести одну строку с сообщением "IMPOSSIBLE".

Пример ввода

5 3 1 1 5 3 2
1.2-3-2-3-
1.**3.**2-
1.1.1=2=1=

Пример вывода

9/3

2. Стрелки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Боб решил вырезать несколько стрелок вида ">>->" из узкой полоски бумаги, на котором были напечатаны символы '–' (минус), '>' (больше) и '<' (меньше). Искажения в виде стрелки недопустимы, например, "древко" стрелки должно состоять точно из одного символа '–'. Вырезанные стрелки должны быть цельными, так как Боб не хочет склеивать стрелки из отдельных кусочков. Также кусочки бумаги нельзя сгибать, но можно поворачивать после разрезания для получения стрелки указанного вида.
Ввод
Во входном файле содержится строка длиной от 1 до `10^5` символов, состоящая только из символов '–', '>', '<'. Это содержимое полоски бумаги, которая есть у Боба.
Вывод
В выходной файл вывести одно целое число – максимальное количество стрелок вида ">>->", которое Боб сможет вырезать из заданной полоски.

Пример ввода

<->>-->>>->>->>->>>->>->>-

Пример вывода

3

3. Кубик Ьубика

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На последнем чемпионате мира по сборке кубика Рубика был установлен новый мировой рекорд. Программист Dan Knights собрал кубик всего за 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` строк с этими действиями, каждое действие на отдельной строке. Любой минимальный вариант решения может быть выведен.

Пример ввода

BWWBBWWB

Пример вывода

2
RU
RU

4. Счастливый билет

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Номер билета состоит из 6 цифр. Эти цифры можно использовать для головоломки, которую можно решать по дороге. Требуется расставить между цифрами номера (не изменяя их порядка) знаки 4 арифметических действий (+, -, * и /) и скобки таким образом, чтобы получилось правильное арифметическое выражение, равное заданному целому числу. Деление разрешается использовать только в случае, если деление производится без остатка. Унарный минус, возведение в степень и другие операции использовать запрещено. Используя один и тот же набор цифр можно получать разные числа. Обычно пытаются получать последовательно все целые числа, начиная с нуля. Например, из номера 111112 можно получить число 0 как (11-11)*12, 1 как 1+(11-11)*2, 2 как 1*(1+1-(1/1))+2 и т.д. Определим уровень "счастья", заложенный в номере билета, как наименьшее неотрицательное целое число, которое нельзя получить, используя цифры номера билета. Таким образом, чем больше уровень "счастья", тем дольше можно решать головоломку.
Ввод
Во входном файле содержится один номер из 6 цифр (от 000000 до 999999).
Вывод
В выходной файл вывести одно целое число – наименьшее неотрицательное целое число, которое нельзя получить, используя цифры заданного номера.

Пример ввода

111112

Пример вывода

29

5. SPAM

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Объем электронной рекламной почты (spam) уже превысил в начале этого года 50% от общего объема почтовых сообщений и быстро растет. Прогнозируют даже, что такой экспоненциальный рост объемов спама может серьезно повлиять на пропускную способность сетей. Наиболее эффективный способ снижения этого трафика – законодательный, но пока соответствующие законы приняты не во всех странах, и приходится использовать специальные программы для сортировки корреспонденции. Спамеры используют различные ухищрения для обхода этих программ. Например, посылают письмо как Web-страницу, где каждый символ обрамлен в теги со случайно сгенерированным содержимым.
Напишите программу, выявляющую письма с текстом, который является результатом случайной генерации. Будем использовать следующие признаки:
  • Письмо содержит слово, в котором есть пять согласных подряд.
  • Письмо содержит слово, в котором есть пять гласных подряд.
  • В письме в словах из пяти или более букв есть в сумме три или более комбинации букв, которые недопустимы в английском языке (например, QE, ZC, YY).
Примечания: Словом будем называть непрерывную последовательность прописных и строчных латинских букв. Регистр букв в этой задаче не важен. Гласными являются буквы A, E, I, O, U, Y. Слова из 4 или менее букв могут быть сокращениями, в которых появление недопустимых комбинаций возможно. В слове YYYYY содержится четыре недопустимых комбинации букв YY.
Ввод
Во входном файле в первой строке содержится одно целое число `K` (`0\ ≤\ K\ ≤\ 100`) – количество недопустимых комбинаций букв. Далее следует `K` строк, содержащих по две латинских буквы – недопустимые комбинации. Далее следует одна или более строк длиной от 1 от 250 символов. Каждая строка содержит текст одного письма.
Вывод
В выходной файл для каждого письма вывести строку с сообщением SPAM, если обнаружен один из признаков случайной генерации, или OK в противном случае.

Пример ввода

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

Пример вывода

SPAM
OK
OK
SPAM
SPAM

6. Soundex Indexing

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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:
  • The first letter of a name appears as the first and only letter in the soundex code.
  • The letters A, E, I, O, U, Y, W and H are never encoded, but do break successive code sequences (see next rule).
  • 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.
  • The soundex code guide is:
    CodeKey Letters and Equivalents
    1B, P, F, V
    2C, S, K, G, J, Q, X, Z
    3D, T
    4L
    5M, N
    6R
  • Trailing zeros are appended to short codes so all names are encoded with a letter followed by three digits.
  • Longer codes are truncated after the third digit.
Input
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.
Output
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.

Sample Input

LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK

Sample Output

         NAME                     SOUNDEX CODE
         LEE                      L000
         KUHNE                    K500
         EBELL                    E140
         EBELSON                  E142
         SCHAEFER                 S160
         SCHAAK                   S200
loading