Yerzhan Utkelbayev

Задача №1.

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У вас есть мультимножества $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$ числа, которые выбираются с текущего мультимножества.

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

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

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

Пример:

Вход

2
5 1
5 0

Ответ

YES
2 3
4 5
1 1
1 0
NO

( Yerzhan Utkelbayev )
комментарий/решение олимпиада

Задача №2.

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

У вас есть $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 \le n \le 100, 1 \le m \le 8$. Оценивается в $11$ баллов.
$1 \le n,m \le 2000$ и $t_i = 1$ для всех кнопок. Оценивается в $15$ баллов.
$1 \le n,m \le 500$. Оценивается в $19$ баллов.
$1 \le n,m \le 10^4$ и $i$-й коридор соединяет комнаты $i$ и $i + 1$. Оценивается в $25$ баллов.
$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

Вход

Ответ

-1

Замечание

{ \center \includegraphics[width=1.0\textwidth]{sample.eps}
} ( Yerzhan Utkelbayev )
комментарий/решение олимпиада