---> 70 задач <---
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
ограничение по времени на тест
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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых \(M\) автобусов, и на каждой остановке висит свое расписание, которое представляет собой набор из \(M\) времен. Плиточный магнат является крупным авторитетом в городе, поэтому расписание соблюдается: от каждой остановки ровно в каждое из указанных времен отправляется автобус. Казалось, что проблема общественного транспорта навсегда решена...

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

Иннокентий решил оценить масштабы трагедии. Для этого он попросил каждого из Q своих друзей сообщить маршрут, по которому они добираются до места работы. Каждый маршрут описывается тремя числами \(u_i\), \(v_i\), \(w_i\): \(u_i\) — это номер остановки, ближайшей к дому i-го друга, \(v_i\) — номер остановки, ближайшей к его работе, а \(w_i\) — номер автобуса,на котором i-й друг едет из дома на работу. При этом с точки зрения i-го друга автобусы нумеруются от \(1\) до \(M\) в том порядке, в котором они отправляются с остановки \(u_i\).

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

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

В первой строке входных данных содержатся два целых числа \(N\) и \(M\) — количество остановок и количество автобусов соответственно (\(2 \le N * M \le 150 000\)). В следующей строке содержатся \(N-1\) целых чисел \(travel_1\), . . . , \(travel_{N-1}\), где \(travel_i\) — минимальное время, необходимое для перемещения между остановками i и i + 1 (\(1 \le travel_i \le 10^9\)).

В следующих \(N\) строках содержатся описания расписаний, каждое из которых представляет собой отсортированный по возрастанию список из \(M\) различных целых чисел \(t_i\) — времен, в которые автобусы должны отправляться с соответствующей остановки (\(1 \le t_i \le 10^9\)).

В следующей строке содержится число T — тип теста (1 или 2). Если T = 1, то это — обычный тест. Тогда на следующей строке содержится целое число Q — количество опрошенных друзей Иннокентия (\(1 \le Q \le 150 000 \)). Далее в Q строках содержатся описания маршрутов друзей, каждое из которых состоит из трех целых чисел \(u_i\), \(v_i\) и \(w_i\): номеров остановок, где начинается и заканчивается поездка i-го друга, и номер автобуса в расписании остановки ui, на котором эта поездка совершается (\(1 \le u_i < v_i \le N, 1 \le w_i \le M\)).

\textbf{Обратите внимание} : дальнейшее описание относится только к последней группе тестов. Если T = 2, то это — тест-серия. Тогда на следующей строке содержатся три целых числа — A, B и K (\(1 \le A, B \le 10^3 , 1 \le K \le 150\)).

В \t{тесте-серии} у Иннокентия Q = (N -1)·M ·K друзей. На каждой из N - 1 остановок, кроме последней, проживает ровно M * K друзей, причем для каждого \(w\) от 1 до M есть ровно K друзей, которые уезжают с этой остановки w-м автобусом.

Остановки, до которых едут K друзей, уезжающих с u-й остановки w-м автобусом, определяются следующим образом. Задается последовательность чисел \(q_i\): \(q_1\) = A, \(q_2\) = B, для i > 2 \(q_i\) = u * \(q_{i-1}\) + w * \(q_{i-2}\) + 42. Тогда i-й из этих K друзей будет ехать до остановки с номером \(v_i\) = u + 1 + (\(q_i\) mod (N - u)), где mod обозначает операцию взятия остатка от деления.

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

Если это обычный тест, то выведите для каждого друга в отдельной строке единственное целое число - искомое максимальное время прибытия на конечную остановку в его маршруте. Если это тест-серия, то выведите единственное целое число — остаток от деления суммы максимальных времен прибытия для всех друзей Иннокентия на \(2^{32}\).

Примечание

Приведем пояснение ко второму тесту из условия.

Это \textbf{тест-серия}. В нем у Иннокентия 5 · 4 · 2 = 40 друзей. Например, с первой остановки вторым автобусом уезжают ровно пять друзей. Поясним, как в этом тесте для них определить конечные остановки. u = 1, w = 2. Строим последовательность \(q_i\): \(q_1\) = 9, \(q_2\) = 10, \(q_3\) = 1 · 10 + 2 · 9 + 42 = 70, \(q_4\) = 1 · 70 + 2 · 10 + 42 = 132, \(q_5\) = 1 · 132 + 2 · 70 + 42 = 314. По ней восстанавливаются конечные остановки для этих пяти друзей Иннокентия: \(v_1\) = 1 + 1 + (9 mod 4) = 3, \(v_2\) = 1 + 1 + (10 mod 4) = 4, \(v_3\) = 1 + 1 + (70 mod 4) = 4, \(v_4\) = 1 + 1 + (132 mod 4) = 2, \(v_5\) = 1 + 1 + (314 mod 4) = 4.

Система оценки

Тесты к этой задаче состоят из шести групп. Каждая группа, кроме нулевой, оценивается в 20 баллов. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов \textbf{предыдущих групп}, исключая тесты из условия. В группах тестов с первой по четвертую включительно вам предлагаются только обычные тесты.

0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3—12. В тестах этой группы \(N = 2, M \le 1 000, Q \le 1 000\).

2. Тесты 13—22. В тестах этой группы \(N = 2, M \le 75 000, Q \le 75 000\).

3. Тесты 23—37. В тестах этой группы \(N * M \le 150 000, N * Q \le 150 000\).

4. В тестах этой группы \(N * M \le 150 000, Q \le 150 000\).

5. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.

Примеры
Входные данные
2 3
1
1 10 21
11 21 31
1
3
1 2 1
1 2 2
1 2 3
Выходные данные
21
21
31
Входные данные
5 2
2 5 3 4
1 3
3 5
10 11
13 14
18 23
2
9 10 5
Выходные данные
667
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.

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

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

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствующем считалке номером \(K\). Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны \(Q\) считалок, соответствующих различным значениям \(K\). Для каждого из этих чисел \(K_i\) необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две команды будут играть в матче с номером \(K_i\).

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

Первая строка входных данных содержит единственное целое число \(N\) — количество команд (2 ≤ \(N\) ≤ 100 000). Вторая строка содержит \(N\) различных чисел от 1 до \(N\) — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди.

Третья строка содержит единственное целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество известных Вере считалок. Каждая из следующих Q строк содержит число \(K_i\) (1 ≤ Ki ≤ 1018) — номер очередного интересующего Веру матча. Обратите внимание, \(K_i\) может быть больше \(N\).

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

Выведите \(Q\) строк: для каждого интересующего Веру числа \(K_i\) два числа в любом порядке — силы команд, сыграющих на \(K_i\)-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Комментарии

Разберем первый тест из условия:

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.

Система оценивания

Тесты к этой задаче состоят из четырех групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–18. В тестах этой группы \(N\) ≤ 2 000, Q = 1, \(K_i\) ≤ 2 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 19–25. В тестах этой группы \(N\) ≤ 100 000, 1 ≤ \(Q\) ≤ 10, \(K_i\) ≤ 100 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
4
1 3 2 4
1
3
Выходные данные
3 4
Входные данные
4
2 1 4 3
3
1
5
2
Выходные данные
2 1
4 2
2 4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.

Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(N\) вершин. Вершина 1 является корнем дерева, а из каждой из оставшихся вершин проведено ребро в некоторую вершину с меньшим номером — ее непосредственного предка.

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

Игроки делают ходы по очереди. Проигрывает тот игрок, к ходу которого на доске не остается шашек.

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

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

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

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

В первой строке находится целое число \(N\) (1 ≤ \(N\) ≤ 500 000) — количество вершин в дереве.

Во второй строке следуют целые числа \(p_2\), \(p_3\), ..., \(p_N\), разделенные пробелами, где \(p_i\) — это номер вершины, являющейся предком вершины \(i\) (1 ≤ pi < i).

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

Выведите единственное целое число — количество партий, в которых Марина одержит победу.

Комментарий

Разберем тест из условия. Доска для игры показана на рисунках ниже. Дети сыграют четыре партии, выбирая в качестве Root вершины 1, 2, 3 и 5. Если выбрать в качестве Root любую из трех оставшихся вершин, на доске исходно не окажется ни одной фишки, поэтому игры не произойдет.

Если выбрать в качестве Root вершину 5, фишки будут исходно находиться в вершинах 6 и 7. В такой партии Марина проигрывает: после того, как она сбивает любую из этих двух фишек с доски, Вова сбивает оставшуюся и заканчивает партию.

Если выбрать в качестве Root вершину 2 или 3, у Марины будет возможность выиграть игру за один ход, щелкнув по фишке из вершины 4 (при этом, в случае Root = 2, она по пути также собьет фишку из 3 вершины по правилам игры)

Можно убедиться, что если выбрать в качестве Root вершину 1, у Марины также будет выигрышная стратегия. Для этого первым ходом Марина должна сбить фишку из вершины 2. Пример партии с таким начальным расположением показан ниже.

Таким образом, Марина выигрывает в трех партиях

Система оценивания

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–17. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов

2. Тесты 18–38. В тестах этой группы \(N\) ≤ 200. Эта группа оценивается в 20 баллов.

3. Тесты 39–59. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.

4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
7
1 2 3 1 5 5
Выходные данные
3
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

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

Дан массив из целых чисел \(a_1\), \(a_2\), . . . , \(a_N\), каждый элемент которого по абсолютной величине не превосходит 2. Найдите такой непустой подотрезок \(a_l\), \(a_l\)+1, . . . , \(a_r\) этого массива (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)), что произведение чисел \(a_l * a_{l+1} * ... * a_r\) является максимально возможным.

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

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

В первой строке входных данных содержится число \(N (1 \le N \le 200 000)\) — число элементов массива. В следующей строке содержатся \(N\) целых чисел \(a_i\) — элементы массива \((|a_i| \le 2\)).

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

В единственной строке выходных данных выведите два числа \(l\) и \(r\) — искомые границы оптимального отрезка (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)). В случае, если ответов несколько, выведите любой из них.

Система оценивания

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп

0. Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 4–15. В тестах этой группы \(N \le 60\). Эта группа оценивается в 30 баллов

2. Тесты 15–31. В тестах этой группы \(N \le 2000\). Эта группа оценивается в 30 баллов.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
5
1 -1 2 2 1
Выходные данные
3 5
Входные данные
3
-1 0 -2
Выходные данные
2 2
Входные данные
7
-1 -2 -1 -2 1 2 -2
Выходные данные
2 7

Страница: << 7 8 9 10 11 12 13 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест