Задача A. Обработка больших данных ≡

Условие

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

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R − L + 1) равна 2ⁱ для некоторого i, а число L делится на 2ⁱ. Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые c₁ ячеек памяти необходимо заполнить значениями v₁, следующие c₂ ячеек — значениями v₂, и так далее, последние c_n ячеек памяти необходимо заполнить значениями v_n, где 1 ≤ v_i ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c₁ = 1, v₁ = 1, c₂ = 2, v₂ = 2, c₃ = 5, v₃ = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:

1. STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
2. STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
3. STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти определяет минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Формат входных данных

Первая строка входных данных содержит три целых числа: k, n и m.

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа c_i и v_i.

Формат выходных данных

Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Ограничения

0 ≤ k ≤ 30, 1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹

1 ≤ c_i ≤ 2^k, 1 ≤ v_i ≤ m, c₁ + c₂ + … + c_n = 2^k

Описание подзадач и системы оценивания

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

Примеры тестов

3 3 2
1 1
2 2
5 1

3

Задача B. Мониторинг труб ≡

Условие

Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p₂, p₃, … , p_n. Для всех i от 2 до n узел с номером p_i соединен односторонней трубой с узлом i, газ по этой трубе передается от узла p_i к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от "a" до "z". Труба, соединяющая узел p_i с узлом i, имеет тип c_i.

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

Каждый запуск робота должен соответствовать одной из m заданных спецификаций, пронумерованных от 1 до m. Спецификация с номером t представляет собой строку s_t, состоящую из строчных букв английского алфавита. Запуск соответствует спецификации s_t, если количество перемещений робота по трубам во время запуска совпадает с длиной s_t, и для всех j от 1 до длины s_t на j-м шаге робот перемещается по трубе, тип которой совпадает с s_t[j] — символом на позиции j в спецификации.

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

Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также, по требованию, список необходимых для этого запусков.

Формат входных данных

В первой строке входных данных находятся три целых числа n, m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий требуется ли вывести список запусков робота, или только их минимальную суммарную стоимость.

В последующих (n − 1) строках содержится информация о трубах, (i − 1)-я из этих строк содержит разделенные пробелом значения p_i и c_i, где p_i — целое число, задающее номер узла, из которого ведет труба в i-й узел, а c_i — строчная буква английского алфавита, задающая тип этой трубы.

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

Формат выходных данных

Первая строка выходных данных должна содержать одно число — минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести −1.

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k — количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа a_i, b_i и c_i — номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Ограничения

1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1

1 ≤ p_i ≤ i − 1

1 ≤ w_i ≤ 10⁹. Суммарная длина строк s_i не превышает 10⁶.

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

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

Необходимо обратить внимание на следующие моменты:

• трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3;
• одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
• робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию «ab» нельзя использовать для проверки труб по маршруту 2→1→6, так как робот не может переместиться из узла 2 в узел 1.

Описание подзадач и системы оценивания

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

Примеры тестов

3 3 0
1 a
2 b
3 a
4 b
2 a

6

7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab

15
4
1 4 1
1 6 2
6 7 2
2 5 3

Задача C. Повышение квалификации ≡

Условие

Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают n сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до n, директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника i имеет номер p_i , причем p_i < i.

Сотрудник x является подчиненным уровня 1 сотрудника y, если p_x = y. Для k > 1 сотрудник x является подчиненным уровня k сотрудника y, если сотрудник p_x является подчиненным уровня k − 1 сотрудника y.

У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа L и R и направить на курсы всех сотрудников с номерами i, такими что L ≤ i ≤ R.

Перед тем, как выбрать числа L и R, директор получил m пожеланий от сотрудников компании, j-е пожелание задается двумя числами u_j и k_j и означает, что сотрудник u_j просит отправить на курсы одного из своих подчиненных уровня k_j. Для экономии средств директор хочет выбрать такие L и R, чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.

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

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

Первая строка входного файла содержит число n — количество сотрудников компании. Вторая строка содержит (n − 1) чисел: p₂, p₃, …, p_n (1 ≤ p_i ≤ i) — номера непосредственных начальников сотрудников.

Третья строка содержит число m — количество пожеланий от сотрудников.

Последующие m строк задают пожелания сотрудников и содержат по два целых числа u_j, k_j (1 ≤ u_j < n, 1 ≤ k_j < n, гарантируется, что у сотрудника u_j есть хотя бы один подчиненный уровня k_j).

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

Необходимо вывести два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.

Ограничения

2 ≤ n, m ≤ 200 000

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

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

На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 — подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 — подчиненным уровня 1 сотрудника с номером 3.

Примеры тестов

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

3 6

Задача D. Полезные ископаемые ≡

Условие

Ведется проект по освоению планеты соседней звездной системы. Для добычи полезных ископаемых планируется направить на планету несколько партий роботов.

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (x_i, y_i).

Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу b_j, содержит n_j роботов и каждый робот партии обладает мобильностью m_j.

Когда партия роботов доставляется на соответствующую базу, каждый робот этой партии перемещается по поверхности планеты от базы до некоторой клетки. Если мобильность робота равна m, он может не более m раз переместиться на одну из восьми соседних клеток, как показано на рис. 1.

Рис. 1. Возможные перемещения робота в восьми направлениях.

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

Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из n_k + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < n_k + 1.

Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более q роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать k, а затем максимизировать z.

Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.

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

Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа x_i, y_i и описывают базы специалистов (1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h).

Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: b_j, n_j и m_j (1 ≤ b_j ≤ s, 1 ≤ n_j ≤ w × h × q, 0 ≤ m_j < max(w, h)).

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

Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < n_k + 1.

Ограничения

1 ≤ w, h ≤ 10⁵, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

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

В приведенном примере описания входных данных следует полностью принять первую партию роботов и дополнительно принять 7 роботов из второй партии. На рис. 2 показано, как можно разместить этих роботов на участке, чтобы в каждой клетке было не более одного робота. Базы специалистов показаны кружками. Клетки, в которых окажутся роботы с базы 1, показаны вертикальной штриховкой, а клетки, в которых окажутся роботы с базы 2, показаны серым цветом.

Рис. 2. Возможное размещение роботов на участке в данном примере.

Описание подзадач и системы оценивания

Баллы за каждую из подзадач 1–5 начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Тесты для подзадачи 6 запускаются только в случае, если все тесты подзадач 1–5 успешно пройдены. Каждый тест в подзадаче 6 оценивается независимо в 1 балл.

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Примеры тестов

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7

Задача E. Гармоническая последовательность ≡

Условие

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел a₁, a₂, …, a_N гармоничной, если каждое число, кроме a₁ и a_N, равно сумме соседних: a₂ = a₁ + a₃, a₃ = a₂ + a₄, …, a_N − 1 = a_N − 2 + a_N. Например, последовательность [1, 2, 1, −1] является гармоничной, поскольку 2 = 1 + 1, и 1 = 2 + (−1).

Рассмотрим последовательности равной длины: A = [a₁, a₂, …, a_N] и B = [b₁, b₂, …, b_N]. Расстоянием между этими последовательностями будем называть величину N(A, B) = |a₁ − b₁| + |a₂ − b₂| + ⋯ + |a_N − b_N|. Например, d([1, 2, 1, −1], [1, 2, 0, 0]) = |1 − 1| + |2 − 2| + |1 − 0| + |−1 − 0| = 0 + 0 + 1 + 1 = 2.

В конце лекции профессор написал на доске последовательность из N целых чисел B = [b₁, b₂, …, b_N] и попросил студентов в качестве домашнего задания найти гармоничную последовательность A = [a₁, a₂, …, a_N], такую, что d(A, B) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние d(A, B).

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

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

Первая строка входного файла содержит целое число N — количество элементов в последовательности.

Вторая строка содержит n целых чисел b₁, b₂, …, b_N.

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

Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Ограничения

3 ≤ N ≤ 300 000; −10⁹ ≤ b_i ≤ 10⁹

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

В приведенном примере оптимальной является, например, гармоничная последовательность [1, 2, 1, −1].

Описание подзадач и системы оценивания

В этой задаче пять подзадач. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

Подзадача 1 (14 баллов)

N = 3, −10 ≤ b_i ≤ 10

Подзадача 2 (14 баллов)

3 ≤ N ≤ 500, −100 ≤ b_i ≤ 100

Подзадача 3 (16 баллов)

3 ≤ N ≤ 100 000, −100 ≤ b_i ≤ 100

Подзадача 4 (16 баллов)

3 ≤ N ≤ 1000, −10⁹ ≤ b_i ≤ 10⁹

Подзадача 5 (40 баллов)

3 ≤ N ≤ 300 000, −10⁹ ≤ b_i ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается баллы за каждую подзадачу.

Примеры тестов

4
1 2 0 0

2

Задача F. Поездка на каникулах ≡

Условие

Железная дорога Флатландии представляет собой прямую, вдоль которой расположены N станций. Будем называть участок железной дороги от некоторой станции до следующей перегоном.

Поезд следует от станции 1 до станции N, делая остановку на каждой станции. В поезде K мест, пронумерованных от 1 до K. На поезд продаются билеты, каждый билет характеризуется тремя числами: S, T и A. Такой билет позволяет проехать от станции S до станции T на месте A.

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

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

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

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

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

Первая строка входного файла содержит числа N, M и K — количество станций, количество уже проданных билетов и количество мест в поезде. Последующие M строк содержат информацию о проданных билетах.

Каждая строка содержит три числа: s_i, t_i и a_i — номер станции, от которой куплен билет, номер станции, до которой куплен билет, и номер места, на которое куплен билет.

Гарантируется, что все билеты куплены таким образом, что ни на каком перегоне ни на какое место нет более одного билета.

Далее идет строка, которая содержит число Q. Последующие Q строк содержат описания вариантов поездки. Каждая строка содержит два числа: f_j, d_j — номер станции, от которой Иван хочет поехать в этом варианте, и номер станции, до которой он хочет поехать.

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

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

Ограничения

2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000, 1 ≤ K ≤ 200 000

1 ≤ s_i < t_i ≤ N; 1 ≤ a_i ≤ K

1 ≤ Q ≤ 200 000; 1 ≤ f_j < d_j ≤ N

Система оценки и описание подзадач

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

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 1 и 2.

Подзадача 1 (33 баллов)

N ≤ 100; M ≤ 100; K ≤ 100, Q = 1

Подзадача 2 (30 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q = 1

Подзадача 3 (37 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q ≤ 200 000

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

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

На перегоне от 2-й до 3-й станции все места заняты, поэтому проехать от 1-й до 5-й станции невозможно. От 3-й до 5-й станции можно проехать, используя два билета: от 3-й до 4-й станции на место 2 и от 4-й до 5-й на место 1. От 4-й до 5-й станции можно проехать, используя один билет на место 1.

Примеры тестов

5 4 3
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5

-1
2
1