#111881

Коллайдер

Темы: [Декартово дерево] [Задачи на моделирование]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача G ]

Физики проводят эксперимент для исследования частиц трёх типов: \(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-й путь

Темы: [Динамическое программирование на таблицах]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача H ]

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

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

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

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

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

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

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

Примеры

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

3 4
abcd
efdg
hijk
4

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

abfdgk

#111893

Бюджет

Темы: [Жадный алгоритм] [Бинарный поиск по ответу]

Всем известно, что основной целью любого крупного правительственного проекта во Флатландии является освоение бюджетных средств (разумеется, по назначению). В настоящее время во Флатландии ведется работа над m национальным проектами, i-й проект может освоить \(s_i\) миллионов Флатландских тугриков в день.

Правительство Флатландии планирует выделить \(n\) грантов для финансирования проектов, каждый по p миллионов Флатландских тугриков. Деньги i-го из грантов будут доступны для освоения, начиная с дня \(r_i\). Когда очередной грант становится доступен для освоения, его можно отдать некоторому проекту. Этот проект осваивает деньги гранта в течение \(\lceil\frac{p}{s_i}\rceil\) дней. Проект не может одновременно осваивать деньги нескольких грантов.

Премьер-министр Флатландии господин Тупиков хочет выяснить, за какое время удастся освоить все деньги, выделенные в рамках грантов. Помогите ему выяснить самый ранний день, когда можно полностью освоить все деньги грантов.

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

Первая строка входного файла "budget.in" содержит числа m, n и p (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ p ≤ \(10^9\)). Вторая строка содержит m целых чисел: \(s_1\), \(s_2\), . . . , \(s_m\) (1 ≤ \(s_i\) ≤ \(10^9\)). Третья строка содержит n целых чисел: \(r_1\),\(r_2\),...,\(r_n\) (1 ≤ ri ≤ \(10^9\)).

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

Первая строка выходного файла "budget.out" должна содержать одно целое число — минимальный день, к которому можно полностью освоить все деньги грантов.

Примечание

Одна из возможных оптимальных схем освоения устроена следующим образом: грант 1 отдается первому проекту, который осваивает его в течение 11 дней. Остальные гранты отдаются второму проекту, грант 2 осваивается в течение дней 3–7, грант 3 в течение дней 8–12 и грант 4 в течение дней 13–17. Заметим, что грант 4 появляется в день 12, но назначается только в день 13.

Примеры

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

2 4 22
2 5
1 3 8 12

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

#111894

Чип и Дейл в лабиринте

Темы: [Наименьший общий предок]

Чип и Дейл спешат на помощь! Но внимательные зрители знают, что помощь как правило нужна самим Чипу и Дейлу, поэтому сегодня вам надо будет сыграть роль сообразительной Гаечки. Итак, Чип и Дейл снова попали в лапы к Толстопузу. Кот очень не любит грызунов и поэтому приготовил им изощренное испытание. Он собирается поместить их в лабиринт и посмотреть смогут ли они из него выбраться. Лабиринт представляет собой дерево, в котором каждое ребро имеет одно направление. Гаечка подслушала разговор Толстопузу со своими сообщниками и теперь знает несколько возможных вариантов: в какую точку лабиринта поместят её друзей, и где будет выход. Для каждого такого варианта она хочет понять, смогут ли Чип и Дейл найти выход, или нет.

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

В первой строке записано число \(n\) (\(n \leq 10^5\)) - количество вершин дерева. В следующих \(n-1\) строках описаны ребра дерева. В \(i+1\)-ой строке записано номера вершин \(a_i, b_i\), означающие, что в дереве есть ребро из вершины \(a_i\) в вершину \(b_i\).

Далее на отдельной строке записано число \(m\) (\(m \leq 10^5\)) -- количество запросов. После этого идут \(m\) строк с описанием запросов, в \(n + 1 + i\)-ой строке записаны через пробел числа \(x_i\) и \(y_i\).

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

Для каждого запроса на отдельной строке требуется вывести Yes, если в графе есть путь между вершинами \(x_i\) и \(y_i\), и No иначе.

input.txt	output.txt
4 1 2 3 1 4 1 6 1 2 3 2 2 3 4 2 4 3 2 1	Yes Yes No Yes No No

#111954

Рассадка участников

Темы: [Задачи на моделирование] [Алгоритмы сортировки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2013, Задача D ]

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

Формат входного файла

Программа получает на вход целое положительное число участников олимпиады \(N \le 1000\). Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

Формат выходного файла

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

Если задача не имеет решения, необходимо вывести одно число 0.

Числа можно выводить как в отдельных строках, так и в одной строке через пробел. Если есть несколько вариантов рассадки, то необходимо вывести любой из них (но только один).

Примеры

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

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

1005 5 1005 2005

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

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

Страница: << 464 465 466 467 468 469 470 >> Отображать по:

Выбрано

:

Отменить

|

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