e-olymp 7365. Серебрянная матрица

Задача

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

Размеры матрицы [latex]n×n[/latex].
Все элементы матрицы лежат во множестве [latex]S = {1, 2, 3, …, 2n-1}[/latex].
Для каждого целого числа [latex]i (1 ≤ i ≤ n)[/latex], все элементы [latex]i-ой[/latex] строки и [latex]i-го[/latex] столбца образуют множество [latex]{1, 2, 3, …, 2n-1}[/latex].
Например, следующая матрица размера [latex]4×4[/latex] является серебряной:

1 2 5 6
3 1 7 5
4 6 1 2
7 4 3 1

Доказано, что серебряная матрица размером [latex]2^K×2^K[/latex] всегда существует. Вам следует построить серебряную матрицу [latex]2^K×2^K[/latex].

Входные данные

Единственное число K [latex](1 ≤ K ≤ 9).[/latex]

Выходные данные

Вывести серебряную матрицу размером [latex]2^K×2^K[/latex]. Для вывода матрицы [latex]2^K×2^K[/latex], следует вывести [latex]2^K[/latex] строки, каждая из которых содержит [latex]2^K[/latex] целых чисел.

Тесты

# Входные данные Выходные данные
1 2 3 1 7 5
4 6 1 2
7 4 3 1
2 1 1 2
3 1
3 3 1 2 5 6 9 10 13 14
3 1 7 5 11 9 15 13
4 6 1 2 12 14 9 10
7 4 3 1 15 12 11 9
8 10 13 14 1 2 5 6
11 8 15 13 3 1 7 5
12 14 8 10 4 6 1 2
15 12 11 8 7 4 3 1

Код программы

Решение задачи

Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

One thought on “e-olymp 7365. Серебрянная матрица

Добавить комментарий