Подразделы

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

Дата и время

06/12/2025 03:41:30

Авторизация

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

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

03/07/2008	Лето 2008 дорешивание ( 4F)
09/07/2008	Лето 2008 - 4 (F)

Назад

Подразделы

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

Дата и время

Авторизация

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

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