| Codeforces Round 627 (Div. 3) |
|---|
| Закончено |
Вам задано поле Тетриса, состоящее из $$$n$$$ столбцов. Начальная высота $$$i$$$-го столбца поля равна $$$a_i$$$ блоков. Сверху на столбцы вы можете ставить только фигуры размера $$$2 \times 1$$$ (то есть высоты $$$2$$$ блока и ширины $$$1$$$ блок). Заметьте, что вы не можете поворачивать эти фигуры.
Ваша задача — определить, возможно ли очистить заданное поле, используя только описанные фигуры.
Более формально, задачу можно описать следующим образом:
Пока хотя бы одно из $$$a_i$$$ больше $$$0$$$, происходит следующий процесс:
- Вы ставите одну фигуру $$$2 \times 1$$$ (выбираете какое-то $$$i$$$ от $$$1$$$ до $$$n$$$ и заменяете $$$a_i$$$ на $$$a_i + 2$$$);
- затем, пока все $$$a_i$$$ больше нуля, каждое $$$a_i$$$ заменяется на $$$a_i - 1$$$.
Ваша задача — определить, возможно ли очистить заданное поле (т.е. завершить описанный процесс), выбирая места для новых фигур правильным образом.
Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов тестовых данных.
Следующие $$$2t$$$ строк описывают наборы тестовых данных. Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество столбцов на поле тетриса. Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), где $$$a_i$$$ равно начальной высоте $$$i$$$-го столбца поля тетриса.
Для каждого набора тестовых данных выведите ответ — «YES» (без кавычек), если вы можете очистить поле тетриса полностью, и «NO» в противном случае.
4 3 1 1 3 4 1 1 2 1 2 11 11 1 100
YES NO YES YES
Первый набор тестовых данных из примера показан ниже:
Серые линии означают границы поля Тетриса. Заметьте, что поле не имеет верхней границы.
Одним из корректных ответов является сначала поставить фигуру в первый столбец. Затем, после второго шага процесса, поле станет равно $$$[2, 0, 2]$$$. Затем надо поставить фигуру во второй столбец и после второго шага процесса поле станет равно $$$[0, 0, 0]$$$.
И второй набор тестовых данных из примера показан ниже:
Можно показать, что вы не можете сделать ничего, чтобы закончить процесс.
В третьем наборе тестовых данных из примера можно сначала поставить фигуру во второй столбец и после второго шага процесса поле станет равно $$$[0, 2]$$$. Затем можно поставить фигуру в первый столбец и после второго шага процесса поле станет равно $$$[0, 0]$$$.
В четвертом наборе тестовых данных из примера можно поставить фигуру в первый столбец, тогда после первого шага процесса поле станет равно $$$[102]$$$, и затем после второго шага процесса поле станет равно $$$[0]$$$.
