Подразделы

Другие разделы

Дата и время

05/04/2025 21:36:16

Авторизация

Лето 4

A. Олимпиада B. Оффшорное программирование C. Многоугольник D. Стена E. Сортировка списка F. Разбиение матрицы G. Обобщённые матрёшки H. Узелки I. Цепные дроби J. Унарная система счисления K. Башня

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

Ограничения: время – 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