Подразделы

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

Дата и время

13/03/2025 15:48:19

Авторизация

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. Разбиение матрицы

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