Codeforces Round 944 (Div. 4) |
---|
Закончено |
У Боба есть таблица с $$$3$$$ строками и $$$n$$$ столбцами, в каждом из которых находится либо $$$a_i$$$, либо $$$-a_i$$$ для некоторого целого числа $$$1 \leq i \leq n$$$. Например, одна из возможных сеток для $$$n=4$$$ показана ниже:
$$$$$$\begin{bmatrix} a_1 & -a_2 & -a_3 & -a_2 \\ -a_4 & a_4 & -a_1 & -a_3 \\ a_1 & a_2 & -a_2 & a_4 \end{bmatrix}$$$$$$
Алиса и Боб играют в игру следующим образом:
Например, предположим, что Алиса дает Бобу массив $$$[1, -1, -1, 1]$$$ для приведенной выше сетки. Тогда произойдет следующее (цвета добавлены для ясности):
$$$$$$\begin{bmatrix} \color{red}{a_1} & \color{green}{-a_2} & \color{blue}{-a_3} & \color{green}{-a_2} \\ -a_4 & a_4 & \color{red}{-a_1} & \color{blue}{-a_3} \\ \color{red}{a_1} & \color{green}{a_2} & \color{green}{-a_2} & a_4 \end{bmatrix} \xrightarrow{[\color{red}{1},\color{green}{-1},\color{blue}{-1},1]} \begin{bmatrix} \color{red}{1} & \color{green}{1} & \color{blue}{1} & \color{green}{1} \\ -1 & 1 & \color{red}{-1} & \color{blue}{1} \\ \color{red}{1} & \color{green}{-1} & \color{green}{1} & 1 \end{bmatrix} \xrightarrow{\text{сортировка каждого столбца}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\,. $$$$$$ Поскольку средняя строка состоит только из $$$1$$$, Алиса выигрывает.
Учитывая сетку Боба, определите, может ли Алиса выбрать массив $$$a$$$ и выиграть игру.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество столбцов сетки Боба.
Следующие три строки содержат по $$$n$$$ целых чисел, $$$i$$$-я из которых содержит $$$g_{i,1}, g_{i,2}, \dots, g_{i,n}$$$ ($$$-n \leq g_{i,j} \leq n$$$, $$$g_{i,j} \neq 0$$$), представляющих сетку Боба.
Если ячейка $$$x > 0$$$ присутствует во входных данных, то эта ячейка в сетке Боба должна содержать $$$a_x$$$; если $$$x < 0$$$ присутствует во входных данных, то эта ячейка в сетке Боба должна содержать $$$-a_{-x}$$$. Для лучшего понимания смотрите пример ввода и примечание.
Для каждого набора входных данных выведите «YES» (без кавычек), если Алиса может выиграть, и «NO» (без кавычек) в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», и «Yes» будут распознаны как положительный ответ).
441 -2 -3 -2-4 4 -1 -31 2 -2 421 2-1 -22 -251 2 3 4 5-2 3 -4 -5 -13 -5 1 2 261 3 -6 2 5 21 3 -2 -3 -6 -5-2 -1 -3 2 3 1
YES NO YES NO
Первый пример описан в условии.
Во втором примере сетка Боба выглядит следующим образом:
$$$$$$\begin{bmatrix} a_1 & a_2 \\ -a_1 & -a_2 \\ a_2 & -a_2 \end{bmatrix}$$$$$$
Чтобы в последнем столбце была $$$1$$$ в средней строке после сортировки, Алиса должна выбрать $$$a_2 = -1$$$. Однако тогда невозможно выбрать $$$a_1$$$ так, чтобы первый столбец имел $$$1$$$ в средней строке после сортировки. Таким образом, Алиса не может выиграть.
В третьем примере Алиса может выбрать $$$a = [1,1,1,1,1]$$$.
Название |
---|