Задача
Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:
Размеры матрицы [latex]n\times n[/latex].
Все элементы матрицы лежат во множестве [latex]S = [/latex]{[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Для каждого целого числа [latex]i \left(1 ≤ i ≤ n\right),[/latex] все элементы [latex]i[/latex]-ой строки и [latex]i[/latex]-го столбца образуют множество {[latex] 1, 2, 3, \ldots, 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\times 2^K[/latex] всегда существует. Вам следует построить серебряную матрицу [latex]2^K\times 2^K[/latex].
Входные данные
Единственное число [latex]K \left(1 ≤ K ≤ 9\right).[/latex]
Выходные данные
Вывести серебряную матрицу размером [latex]2^K×2^K[/latex]. Для вывода матрицы [latex]2^K\times 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> using namespace std; void create(int** x, int k) { if (k == 1) { x[0][0] = 1; x[0][1] = 2; x[1][0] = 3; x[1][1] = 1; } else { create(x, k - 1); int from = 1 << (k - 1), n = 1 << k; for (int i = from; i < n; i++) for (int j = from; j < n; j++) x[i][j] = x[i - from][j - from]; for (int i = 0; i < from; i++) for (int j = 0; j < from; j++) { x[i + from][j] = x[i][j] + n; x[i][j + from] = x[i][j] + n; } for (int i = 0; i < from; i++) x[i + from][i]--; } } int main() { int k, n = 1; scanf("%d", &k); n <<= k; int** x = new int*[n]; for (int i = 0; i < n; i++) x[i] = new int[n]; create(x, k); for (int i = 0; i < n; i++) { printf("%d", x[i][0]); for (int j = 1; j < n; j++) printf(" %d", x[i][j]); printf("\n"); } return 0; } |
Решение задачи
Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая [latex]k = 1[/latex] подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю [latex]k = 1[/latex] и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.
Ссылки
Ссылка на e-olymp
Ссылка на ideone