printЛето 4

printF. Разбиение матрицы

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Правильным разбиением квадратной матрицы, состоящей из `n^2` ячеек, называется разбиение ячеек на `n` подмножеств по `n` ячеек в каждом. Причём каждое подмножество ячеек является связным. На рисунке 1 показано правильное разбиение матрицы, а на рисунке 2 – неправильное.
1 1 1 5 5
2 1 5 5 4
2 1 5 4 4
2 2 4 4 3
2 3 3 3 3
Рис. 1
1 1 1 4 5
2 1 5 4 5
2 1 5 5 4
2 2 4 4 3
2 3 3 3 3
Рис. 2
Напишите программу, которая определяет, является ли разбиение квадратной матрицы правильным.
Ввод
Входной файл начинается строкой, содержащей одно целое число `N` – размер матрицы (`0\ <\ N\ <\ 100`). В следующих `N\ -\ 1` строках записано разбиение ячеек матрицы на подмножества. Каждая строка содержит `2*N` целых чисел – описание одного подмножества в формате `a_1\ a_2\ a_3\ a_4\ …`, что означает: ячейки `(a_1,\ a_2)`, `(a_3,\ a_4)`, … принадлежат к одному подмножеству. Последнее подмножество состоит из ячеек, не входящих в подмножества 1, 2, …, `N\ -\ 1`.
Вывод
Запишите в выходной файл слово "good", если разбиение правильное, или слово "wrong" в противном случае.

Пример ввода 1

2
1 2 2 1

Пример вывода 1

wrong

Пример ввода 2

5
1 1 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4

Пример вывода 2

good

Пример ввода 3

5
1 1 1 2 1 3 3 2 2 2
2 1 3 1 4 1 5 1 4 2
4 5 5 2 5 3 5 5 5 4
2 4 1 4 3 5 4 3 4 4

Пример вывода 3

wrong
Источник: Весенний турнир имени Мартовского Зайца, 2007
loading