Страница: 1 2 3 4 >> Отображать по:

#30

T2005

Темы: [Бор] [Бинарный поиск]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2005, Задача E ]

Клавиатура сотового телефона выглядит так:

1 — пробел

2 — abc

3 — def

4 — ghi

5 — jkl

6 — mno

7 — pqrs

8 — tuv

9 — wxyz

Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.

Если для ввода какого-то слова нужно нажать последовательность клавиш, которая может являться началом какого-то другого слова, то после ввода этого слова нужно нажать клавишу 1, что соответствует вводу пробела. При вводе пробела считается, что вы ввели все слово целиком (а не только какое-либо его начало). Если после ввода пробела оказалось, что в словаре такой последовательности клавиш удовлетворяет несколько слов, подставляется первое из них в алфавитном порядке. Если (опять же после ввода пробела) оказалось, что в словаре нет слова, которое может быть введено такой последовательностью клавиш, то все, что было введено после предыдущего пробела (введенного или автоматически подставленного, или, если в тексте ранее не встречалось ни одного пробела — от начала текста) удаляется. Если после ввода пробела (как нажатием "1", так и автоподстановкой) или в начале текста нажимается клавиша "1", то ее нажатие игнорируется.

Вам дан словарь и последовательность нажатий клавиш. Выведите текст, который был введен пользователем.

Примечание: в тексте используются только маленькие латинские буквы и символ пробел.

Входные данные

Сначала на вход программы поступает число N — количество слов в словаре (2≤N≤100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.

Далее вводится число M — количество нажатий клавиш (1≤M≤20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".

Выходные данные

Выведите одну строку — текст, который оказался введен пользователем. Пробел после последнего введенного слова также должен быть выведен.

Примечание:

2
a
z
2
5 1

Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел.

Оценка задачи

1 балл получат программы, правильно решающие задачу при ограничениях 2≤N≤100, 1≤M≤200.

Примеры

Входные данные

5
po
pod
sasha
shla
shosse
12
7 4 5 7 2 7 6 1 7 4 6 1

Выходные данные

shla sasha po shosse

Входные данные

2
sem
vosem
6
7 8 9 7 8 1

Выходные данные

sem vosem

#40

Перекраска клеток

Темы: [Система непересекающихся множеств] [Двумерные массивы] [Список]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2006, Задача E ]

+

+

(4,3)

+

+

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

закрасить клетку (i,j) в черный цвет.
для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.

Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

Входные данные

Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 10⁵), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

Выходные данные

На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.

Оценка задачи

1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.

Примеры

Входные данные

5 5 6
Color 4 2
Neighbors 4 3
Color 2 3
Color 3 3
Neighbors 4 3
Neighbors 5 1

Выходные данные

#45

Контейнеры

Темы: [Эвристические методы] [Стек]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2006, Задача J ]

На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида — во вторую стопку и т.д.

Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.

Входные данные

В первой строке задается одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число k_i — количество контейнеров в стопке, а затем k_i чисел — виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

Выходные данные

Выведите описание действий автопогрузчика: для каждого действия укажите два числа — из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, выдайте одно число 0. Если контейнеры изначально правильно размещены по стопкам, выводить ничего не надо.

Оценка задачи

1 балл будут получать программы, верно работающие при следующих ограничениях: количество стопок не больше 10, в каждой стопке не более 10 контейнеров.

Комментарий к примеру:

Изначально в первой стопке лежат четыре контейнера — снизу контейнер с товаром первого вида, над ним — с товаром второго вида, над ним — третьего, и сверху — еще один контейнер с товаром второго вида.

Одна из правильных последовательностей действий (вместо ответа в примере задачи):

1 2
1 3
1 2

Примеры

Входные данные

Выходные данные

#412

Переключение между окнами

Темы: [Список] [Задачи на моделирование]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача J ]

Дан список вызываемых программ (при вызове программы она добавляется в начало списка активных программ). Также могут осуществляться переключения между программами (задается номер программы в списке и она переходит в начало списка). Требуется вывести название первой программы из списка при каком-либо его изменении.

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

Задана последовательность действий пользователя, где каждое действие – либо запуск приложения, либо переключение между окнами. Выведите список имен приложений в том порядке, в котором с ними работал пользователь.

Входные данные

В первой строке вводится целое число n – количество действий пользователя ( 1 $le$ n $le$ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

Выходные данные

Выведите n строк – последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.

Примеры

Входные данные

6
Run Mozilla Firefox
Run Free Pascal
Alt+Tab
Run Miranda IM
Alt+Tab+Tab
Alt+Tab+Tab+Tab

Выходные данные

Mozilla Firefox
Free Pascal
Mozilla Firefox
Miranda IM
Free Pascal
Free Pascal

#523

Терминал

Темы: [Дерево отрезков, RSQ, RMQ]

Источники: [ Командные олимпиады, ВКОШП, 2003, Задача H ]

Над двумерной таблицей введена операция A, которая по координатам клетки, направлению и числу, прибавляет это число ко всем ячейкам от начальной в заданном направлении. Также определена операция B, которая вызывает операцию A для всех ячеек заданного прямоугольника.

Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из m×n ячеек, каждая из которых может содержать произвольное целое число. Ячейки занумерованы парами чисел, левая верхняя ячейка имеет номер (1, 1), правая нижняя – ($m$, $n$).

Специальное устройство ввода, сконструированное специально для этого терминала, позволяет отправлять терминалу две команды: $A$($r$, $c$, $d$, $v$) и $B$($r_1$, $c_1$, $r_2$, $c_2$, $d$, $v$).

Рассмотрим сначала команду $A$. Параметры $r$ и $c$ изменяются в пределах от 1 до $m$ и от 1 до $n$ соответственно и указывают, к какой ячейке применяется команда. Параметр $d$ может принимать значение из множества {$L$, $R$, $U$, $D$} и задает направление, в котором применяется команда: влево, вправо, вверх или вниз соответственно. Параметр $v$ представляет собой целое неотрицательное число. В результате выполнения команды значения во всех ячейках, находящихся в направлении $d$ от ячейки ($r$, $c$), включая эту ячейку, увеличиваются на $v$.

Например, если терминал имеет размер 5×4, то после выполнения команды $A$(3, 2, $R$, 3) значения в ячейках (3, 2), (3, 3) и (3, 4) увеличатся на 3, а после команды $A$(2, 1, $U$, 2) значения в ячейках (2, 1) и (1, 1) увеличатся на 2.

Рассмотрим теперь команду $B$. Первые четыре ее параметра являются целыми числами и удовлетворяют условиям 1$ \le$ $r_1$ $\le$ $r_2$ $\le$ $m$ и 1$ \le$ $c_1$ $\le$ $c_2$ $\le$ $n$. Параметры $d$ и $v$ могут принимать те же значения, что и соответствующие параметры команды $A$. Команда $B$ выполняется следующим образом: для всех пар ($r$, $c$), таких, что $r_1$ $\le$ $r$ $\le$ $r_2$ и $c_1$ $\le$ $c$ $\le$ $c_2$ выполняется команда $A$($r$, $c$, $d$, $v$).

Исходно все ячейки терминала содержат нули. Выведите содержимое терминала после выполнения заданной последовательности команд.

Входные данные

В первой строке вводятся числа $m$ и $n$, ( 1$ \le$m, n$ \le$200). В следующей строке задается число $k$ – количество команд, которые следует обработать ( 0$ \le$k$ \le$40 000). Далее идут $k$ строк, содержащих описания команд. Первый символ каждой строки задает тип команды, затем следует пробел и параметры команды, каждые два последовательных параметра разделены ровно одним пробелом. Параметр $v$ каждой команды неотрицателен и не превышает 100.

Общее число команд $A$, которое потребуется выполнить на терминале, включая команды, которые придется выполнить при выполнении команд $B$, не превышает 5 * $10^6$.

Выходные данные

Выведите $m$ строк по $n$ чисел в каждой – содержимое терминала после выполнения указанной последовательности команд.

Примеры

Входные данные

5 4
4
A 2 2 D 1
A 3 4 L 2
B 2 3 3 4 U 13
B 1 1 2 1 R 5

Выходные данные

Страница: 1 2 3 4 >> Отображать по:

Выбрано

Отменить

Добавить в контест