Задача A. Темные комнаты

У вас есть $n$ комнат, которые соединены $n$-$1$ коридорами. Известно, что с любой комнаты можно дойти до любой другой. В каждой комнате есть ровно одна лампочка. Есть $m$ кнопок пронумерованных от $1$ до $m$, кнопка с номером $i$ включает или выключает лампочки во всех комнатах на пути с комнаты $v_i$ до комнаты $u_i$. Состояние комнаты задается одним числом $0$ или $1$, где $0$ означает лампочка выключена, а $1$ означает, что она включена. Алан пришел в гости к вам. Вы узнали, что Алан будет чуствовать себя как дома, если состояния комнат будут $a_1$, $a_2$, ..., $a_n$ для комнат от $1$ до $n$. Вы должны найти какие кнопки и в каком порядке нажимать, чтобы Алан чуствовал себя как дома. Так как вы не хотите заставлять ждать гостя, в последовательности не может быть больше чем $10^5$ кнопок. Если невозможно найти такую последовательность, вы должны вывести -$1$. Изначально все лампочки во всех комнатах выключены. В первой строке входных данных задается одно целое число $n$ ($1 \le n \le 10^4$) — количество комнат. Во второй строке задаются $n$ чисел: $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 1$) желаемое состояния комнат. Каждая из следующих $n$-$1$ строк описывает один коридор двумя целыми числами $v$ и $u$ ($1 \le u, v \le n$), что означает есть корридор между комнатами $v$ и $u$. В следующей строке задается одно целое число $m$ ($1 \le m \le 10^4$) — количество кнопок. В каждой из следующих $m$ строк задается описание кнопок: в $i$-й строке описание $i$-й кнопки три целых числа $u_i$, $v_i$ и $t_i$, где $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$) комнаты которые описывают путь, $t_i$ равно $0$, если кнопка выключает лампочки или $1$, если она включает лампочки. Выведите `-$1$'(без кавычек), если невозможно найти нужную последовательность. Иначе, выведите $l$ количество кнопок в последовательности и в следущей строке выведите $l$ чисел — номера кнопок в порядке из нажатия. Данная задача содержит пять подзадач:

1. $1 \le n \le 100, 1 \le m \le 8$. Оценивается в $11$ баллов.
2. $1 \le n,m \le 2000$ и $t_i = 1$ для всех кнопок. Оценивается в $15$ баллов.
3. $1 \le n,m \le 500$. Оценивается в $19$ баллов.
4. $1 \le n,m \le 10^4$ и $i$-й коридор соединяет комнаты $i$ и $i + 1$. Оценивается в $25$ баллов.
5. $1 \le n,m \le 10^4$. Оценивается в $30$ баллов.

s Вход

6
1 1 0 0 1 1
1 2
1 3
3 4
3 5
4 6
4
1 2 1
2 5 1
3 4 0
1 6 1

Ответ

3
4 2 3

Вход

3
0 0 1
1 3
1 2
1
1 3 1

Ответ

-1

{ \center \includegraphics[width=1.0\textwidth]{sample.eps}
}

Задача B. Охрана природы

Темирулан — активист охраны природы и защиты животных округа Каспий. Недавно во время прогулки по родному краю он обнаружил редкое растения типа ЖранУ. Растения ЖранУ являются особенными. Они растут только в тени под большими, старыми деревьями. Темирулан проверил $n$ подряд идущих деревьев, и для каждого из них узнал можно ли под ним посадить растение ЖранУ. Темирулану растение ЖранУ сильно понравилось, и он решил, что каждый год в течении следующих $q$ лет будет делать посадку этого растение. При посадке растения он выбирает некоторое количество подряд идущих деревьев от $l$ до $r$, и под каждым деревом делает посадку растение ЖранУ если можно посадить. После посадки растения их обязательно нужно полить, каждый год Темирулан поливает все растения посаженные в этот год. Для поливки растения Темирулан взял с собой ведро размера $k$, которым можно полить все растения ЖранУ которые растут под $k$ подряд идущими деревьями. Темирулан хочет полить каждое посаженное растение хотя бы один раз. Какое минимальное количество ведер воды для поливки всех новых посаженных растении? Обратите внимание, каждый год Темирулан поливает растения не учитывая предыдущий год. Первая строка входных данных содержит два целых числа $n$ и $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — количество деревьев и константное число для чтения входных данных. Далее следующие $n$ чисел описывает $i$-е дерево — если $i$-е число 0, то нельзя посадить растение под $i$-м деревом, иначе можно. Деревья нумеруются с нуля. В следующей строке число $q$ $(1 \le q \le 2\cdot10^5)$ — количество посадок растений. Затем в следующих $q$ строках даны по три целых числа: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Обратите внимание, что концы отрезков $[l_i, r_i]$ и число $k_i$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} где $lastans$ — последний ответ на запрос (изначально $lastans$ равен $0$). Если значение $l_i$ получилось больше значения $r_i$, то нужно поменять местами значения $l_i$ и $r_i$. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$.

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

Выведите $q$ строк. В $i$-й строке выведите одно число — ответ для $i$-го запроса.

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

Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 100$, $k_i = 1$, $t = 0$. Оценивается в $7$ баллов.
2. $n \le 2000$, $q \le 2000$. Оценивается в $12$ баллов.
3. $n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . Оценивается в $21$ баллов.
4. $n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . Оценивается в $23$ баллов.
5. Ограничения из условия задачи. Оценивается в $37$ баллов.

Пример:

Вход

7 0
0 1 1 0 1 1 0
6
0 2 1
0 6 0
0 6 1
1 4 2
0 6 5
1 5 5

Ответ

1
4
2
2
1
1

Задача C. Претенденты на ГОИ

Каждые четыре года среди всех стран проводится <<Гладиаторская Олимпиада по Информатике>>. Это уникальное в своем роде соревнование, в котором участникам нужно иметь не только силу, но и высокий интеллект. В Берляндии сейчас приятная головная боль, в стране $N$ различных претендентов на Олимпиаду. Уровень каждого претендента обозначается числом, $i$-й претендент имеет уровень $i$. Берляндии как сильной в информатике стране разрешено отправлять любое количество участников на Олимпиаду, но в стране все равно планируют провести отбор. На отборочный раунд выбирается некоторое ненулевое количество претендентов, затем проводят $M$ туров. Далее в $i$-м туре проделываются следующие операции:

1. Если количество оставшихся претендентов хотя бы $a_i$, то список претендентов покидают $a_i$ претендентов с минимальным уровнем. Далее заново повторяется $i$-й тур.
2. Если количество оставшихся претендентов строго меньше чем $a_i$, то переходится к следующему туру. За исключением случая когда $i=M$, в этом случае отбор завершается.

Заметим тот факт, что после выбора претендентов на отборочные туры финальный список оставшихся претендентов определяется однозначно. Журналисты решили заранее описать всевозможные случаи и посчитать общее количество оставшихся претендентов по всем возможным изначальным выборкам претендентов. Так как это значение может быть большим выведите остаток по модулю $P$. В первой строке входных данных даны три целых числа $M$, $N$ и $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — количество раундов, количество претендентов и число по которому надо взять остаток. Заметим, что $P$ необязательно простое число. В следующей строке даны $M$ целых чисел $a_i$ ($1 \le a_i \le 1000$) — число для $i$-го раунда. Выведите одно целое число — ответ на задачу. Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 18$. Оценивается в $10$ баллов.
2. $n \le 1000$. Оценивается в $18$ баллов.
3. $n \le 10^6$, $P = 999999937$. Оценивается в $21$ баллов.
4. Только ограничения из условия. Оценивается в $51$ баллов.

Вход

3 4 100000
7 3 4

Ответ

17

Задача D. Разница

У вас есть мультимножества $S$. Разница мультимножества и множества состоит в том, что в мультимножестве одно и то же число может содержаться несколько раз, а в множестве — только один раз. Изначально, в мультимножестве содержатся все целые числа от $1$ до $n$ по одному разу. За одну операцию вы можете убрать два числа $a$ и $b$ из мультимножества и добавить их абсолютную разницу |$a$ - $b$|. Вы хотите выполнить некоторые операции так, чтобы в мультимножестве было только одно число $x$. В первой строке входных данных задается одно целое число $T$ ($1 \le T \le 100$) — количество тестов. В следующих $T$ строках задаются по два целых числа $n$ и $x$ ($2 \le n \le 10^5, 0 \le x \le n$) — описание теста. Сумма всех $n$ по всем тестам не превышает $5 \cdot 10^5$. Для каждого теста выведите "NO" (без кавычек), если невозможно получить $x$. Иначе, для этого теста выведите "YES" (без кавычек) и в следующих $n$-$1$ строках выведите операции в порядке их выполнения. Для каждой операции выведите два целых числа $a$ и $b$ числа, которые выбираются с текущего мультимножества. Данная задача содержит четыре подзадачи, в каждой подзадаче выполняются ограничения из условий:

1. $2 \le n \le 4$. Оценивается в $12$ баллов.
2. $n$-нечетное и $x = (n + 1) / 2$. Оценивается в $15$ баллов.
3. $0 \le x \le 1$. Оценивается в $23$ баллов.
4. $2 \le n \le 10^5$. Оценивается в $50$ баллов.

Вход

2
5 1
5 0

Ответ

YES
2 3
4 5
1 1
1 0
NO

Задача E. Na2a и уравнение

Na2a много баловался на уроке информатики, и учитель в наказание ему придумал следующую задачу. Найти неотрицательное целое число $x$, такое что ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$, где $a_1,...,a_n,S$ — заданные числа. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Помогите Na2a решить данное уравнение.

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

В первой строке находятся два целых числа $n$, $S (1 \le n \le 10^5, 0 \le S \le 10^{12})$. Во второй строке находятся $n$ целых числа $a_1$, $a_2$, ..., $a_n(0 \le a_i \le 10^{12})$.

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

Выведите -$1$, если уравнение не имеет неотрицательных решений. Иначе выведите такое $x(x \ge 0)$, что описанное в условии равенство выполняется. Если существует несколько ответов, выведите любой из них.

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

Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условии и:

1. $n \le 1000, a_i,s \le 1000$. Оценивается в $7$ баллов.
2. $n = 2, a_i,s \le 10^{12}$. Оценивается в $22$ баллов.
3. $n \le 10^4, a_i,s \le 10^6$. Оценивается в $20$ баллов.
4. $n \le 10^5, a_i,s \le 5 \cdot 10^7$. Оценивается в $16$ баллов.
5. $n \le 10^5, a_i,s \le 10^{12}$. Оценивается в $35$ баллов.

Пример:

Вход

3 4
1 2 3

Ответ

2

\Note Таблица для исключающего ИЛИ.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Например, если $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ тогда: $X$ $\oplus$ $Y$ = $68_{10}$ = $1000100_{2}$.

Задача F. Тренерский выбор Тимы

Тима с недавних пор начал тренировать баскетбольные команды. Капитаном команды всегда выбирается игрок с максимальным ростом. Также он придумал свою формулу несовместимости игроков в одной команде. Формула зависит от роста всех игроков в команде. Несовместимость игроков в одной команде равняется сумме разниц роста между всеми игроками и ростом капитана. Более формально, пусть $h_1, h_2, ... , h_m$ это рост игроков команды, $mx = max(h_1, h_2, ..., h_m)$, тогда несовместимость = $\sum_{i=1}^{m} mx$-$h_i$. У Тимы есть $n$ игроков выстроенных в ряд, $i$-й из них имеет рост $a_i$. Он хочет разбить всех на $k$ команд, каждый игрок должен быть в ровно одной команде и команда должна состоять из игроков, которые составляют непрерывный отрезок в ряду. Тима хочет собрать команды так, чтобы суммарная несовместимость была минимальной. Помогите Тиме разбить на команды оптимально. Первая строка входных данных содержит два целых чисел $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le min(n, 20)$) — количество игроков в ряду и количество команд. Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 10^6$) — рост $i$-го игрока слева в ряду в сантиметрах. Выведите единственное целое число — ответ на задачу. Данная задача содержит шесть подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 100$, $k = 1$. Оценивается в $5$ баллов.
2. $n \le 2000$. Оценивается в $11$ баллов.
3. $k = 2$. Оценивается в $8$ баллов.
4. $k = 3$. Оценивается в $15$ баллов.
5. $a_i \le a_{i+1}$, для всех $1 \le i < n$. Оценивается в $19$ баллов.
6. Ограничения из условия задачи. Оценивается в $42$ баллов.

Вход

7 3
6 4 1 5 3 2 2

Ответ

7

Вход

5 2
4 1 5 5 6

Ответ

5

Вход

9 2
3 7 4 1 3 2 4 6 7

Ответ

22