Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 7 задач <---
Источники --> Личные олимпиады --> Жаутыковские олимпиады
    2011(8 задач)
Страница: << 1 2 Отображать по:
#111881
Коллайдер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Физики проводят эксперимент для исследования частиц трёх типов: \(x\), \(y\) и \(z\). Они запускают в коллайдер пронумерованный ряд из \(n\) частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с \(i\)-ого места ряда и моментально появляется на месте \(j\). После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте \(k\). Напишите программу, которая поможет физикам.

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

В первой строке файла два целых числа: \(n\) – количество частиц и m — общее количество воздействий и вопросов (1 \(\le\) \(n\) \(\le\) 1000000, 1 \(\le\) \(m\) \(\le\) 15000). Во второй строке — последовательность из символов \(x\), \(y\) и \(z\) длиной \(n\). На каждой из следующих \(m\) строк (1 \(\le\) \( m\) \(\le\) 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом \(a\) и после пробела дается два целых числа из интервала [1; \(n\)]. Первое из них показывает начальное, а второе  конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом \(q\) и после пробела дается одно целое число из интервала [1; \(n\)]. Оно указывает позицию, которая интересует физиков.

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

Выведите столько строк, сколько вопросов во входном файле. В строке номер \(i\) надо записать ответ на вопрос \(i\) — название соответствующей частицы \(x\), \(y\) или \(z\).

Пояснения к примеру

Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,

Примеры
Входные данные
15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q 2
Выходные данные
y
z
y
#111882
K-й путь
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У вас есть таблица c \(N\) строками и \(M\) столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка  значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение \(K\)-го пути в этом отсортированном листе.

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

В первой строке задается два целых числа \(N\)  количество рядов и \(M\)  количество столбцов заданной таблицы (1 \(\le\) \(N\), \(M\) \(\le\) 30). Каждая из следующих \(N\) строк содержит ровно \(M\) строчных букв английского алфавита. Последняя строка входного файла содержит целое число \(K\) (1 \(\le\) \(K\) \(\le\) 1018). Гарантируется, что для \(K\) ответ всегда существует.

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

Первая и последняя строка выходного файла должна содержат одну строку - ответ к задаче.

Пояснения к примеру

abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk

Примеры
Входные данные
3 4
abcd
efdg
hijk
4
Выходные данные
abfdgk
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест