--->
8 задач
<---
При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.
Проверяющей программе доступно три блока информации:
Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.
Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.
Входные данные всегда корректны. Это означает, например, что ответ участника не нужно проверять на соответствие формату и что ответ жюри точно правильный.
Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.
Тесты состоят из четырёх групп.
4 2 3 0 4 1 6 0 5 2 2 1 0 3 4 0 0
OK WA WA OK
Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.
Мелодия состоит из \(M\) нот \(b_1, b_2, \dots, b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.
В первой строке входного файла содержатся три целых числа \(N\), \(M\), \(L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i\) (\(i = 1, 2, \dots N\)) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i\) (\(i = 1, 2, \dots M\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.
Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.
Тесты состоят из четырёх групп.
6 8 179 4 9 23 15 43 7 3 10 14 7 3 8 7 3
0
5 8 5 5 3 8 14 1 10 7 3 7 12 3 3 6
4
2 2 4 6 13 8 10
1
Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.
Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).
Выведите единственное число - суммарное количество обгонов.
Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.
2 1 20 19
0
5 3 3 6 2 4 1
7
В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.
Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.
Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.
Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.
В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.
Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.
Тесты состоят из четырёх групп.
8 5 3 3 3 3 3 7 1
1 2
Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых \(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