#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

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

#579

Программа психологического исследования программистов

Темы: [Хеш]

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

Компания "Макрохард" заказала у одного известного психолога полное психологическое обследование всех работников компании. Психолог, привлеченный для проведения обследования, известен своим инновационным методом, позволяющим составить полную психологическую картину сотрудника по наиболее часто используемому им в программах идентификатору. Однако, к сожалению, программа, используемая в анализе, оказалась неожиданно испорчена вирусом, поэтому требуется срочно написать новую. Помогите известному психологу. Напишите программу, которая по приведенной программе выяснит наиболее часто используемый в ней идентификатор.

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

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

В первой строке вводятся число n - количество ключевых слов в языке (0 <= n <= 50) и два слова C и D, каждое из которых равно либо "yes", либо "no". Слово C равно "yes", если идентификаторы и ключевые слова в языке чувствительны к регистру символов, и "no", если нет. Слово D равно "yes", если идентификаторы в языке могут начинаться с цифры, и "no", если нет.

Следующие n строк содержат по одному слову, состоящему из букв латинского алфавита и символов подчеркивания - ключевые слова. Все ключевые слова непусты, различны, при этом, если язык не чувствителен к регистру, то различны и без учета регистра. Длина каждого ключевого слова не превышает 50 символов.

Далее до конца входных данных идет текст программы. Он содержит только символы с ASCII-кодами от 32 до 126 и переводы строки.

Размер входных данных не превышает 10 килобайт. В программе есть хотя бы один идентификатор.

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

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

Примеры

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

0 yes no
int main() {
  int a;
  int b;
  scanf("%d%d", &a, &b);
  printf("%d", a + b);
}

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

int

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

0 yes no
#define INT int
int main() {
  INT a, b;
  scanf("%d%d", &a, &b);
  printf("%d %d", a + b, 0);
}

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

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

6 no no
program
var
begin
end
while
for
program sum;
var
  A, B: integer;
begin
  read(A, b);
  writeln(a + b);
end.

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

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

1 yes yes
_
a = 0h
b = 0h
c = 0h

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

0h

#2980

Откат

Темы: [Дерево отрезков, RSQ, RMQ] [Персистентные структуры данных]

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

Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.

В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.

На данный момент у Сергея хранятся $n$ точек восстановления различных серверов, пронумерованных от 1 до $n$. Точка восстановления с номером $i$ позволяет произвести откат для сервера $a_i$. Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами $l, l + 1, \ldots, r$ для некоторых $l$ и $r$.

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного $l$, при каком минимальном $r$ в процессе переноса будут доступны точки восстановления не менее чем $k$ различных серверов.

Помогите Сергею.

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

Первая строка входного файла содержит два целых числа $n$ и $m$ ($1 \le n, m \le 10^5$), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ — номера серверов, которым соответствуют точки восстановления ($1 \le a_i \le m$).

Третья строка входного файла содержит $q$ — количество запросов, которые необходимо обработать ($1 \le q \le 100\,000$). В процессе обработки запросов необходимо поддерживать число $p$, исходно оно равно 0. Каждый запрос задается парой чисел $x_i$ и $y_i$, используйте их для получения данных запроса следующим образом: $l_i = \left((x_i + p) \bmod n\right) + 1$,

$k_i = \left((y_i + p) \bmod m\right) + 1$ ($1 \le l_i,x_i \le n$, $1\le k_i, y_i \le m$). Пусть ответ на $i$-й запрос равен $r$. После выполнения этого запроса, следует присвоить $p$ значение $r$.

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

На каждый запрос выведите одно число — искомое минимальное $r$, либо 0, если такого $r$ не существует.

Примеры

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

7 3
1 2 1 3 1 2 1
4
7 3
7 1
7 1
2 2

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