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 )
комментарий/решение олимпиада