Задача №115387. Хорошие раскраски 6
Нокотан большой фанат раскрашивания табличек. Она придумала число \(c\) (\(1 \leq c \leq 17\)) и решила, что перед входом в здание клуба должна висеть таблица со следующими свойствами:
- Высота таблицы \(h\) и ширина таблицы \(w\) удовлетворяют ограничениям (\(1 \leq h, w \leq 1500\)).
- Каждая клетка может быть раскрашена в какое-то подмножество из \(c\) цветов (возможно пустое). Формально пусть \(a_{i, j}\) — число, записанное в таблице в клетке с координатами \(i, j\), тогда \(0 \leq a_{i, j} < 2^c\) и считается, что клетка покрашена в том числе в цвет с номером \(k\) (\(0 \leq k < c\)), если \(\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1\).
- Пусть \(1 \leq x < 2^c\) и \(cnt_x\) — число клеток, на которых записано число \(x\). Тогда должно выполняться неравенство \(1 \leq cnt_x \leq 20\).
- Каждый цвет образует одну компоненту связности. Формально для любого \(0 \leq k < c\) клетки, в которых \(k\)-й бит записи ненулевой (\(\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1\)), образуют одну компоненту связности. (Две клетки находятся в одной компоненте связности, если от одной из них можно добраться до второй, переходя в соседние четыре по горизонтали или вертикали клетки множества).
Помогите Нокотан найти таблицу, удовлетворяющую всем свойствам для заданного \(c\).
В единственной строке входных данных содержится целое число \(c\) (\(1 \leq c \leq 17\)) — количество цветов, в которые должна быть раскрашена таблица.
В первой строке выведите пару целых чисел \(h, w\) (\(1 \leq h, w \leq 1500\)) — высота и ширина таблицы соответственно. В следующих \(h\) строках выведите по \(w\) целых чисел \(a_{i, j}\) (\(0 \leq a_{i, j} < 2^c\)) — значения в таблице. Таблица должна удовлетворять четырем условиям, описанным в условии задачи.
Во втором тестовом примере клетки, покрашенные в цвет с номером \(0\), имеют координаты \((0, 0)\) и \((1, 0)\) и поэтому образуют \(1\) компоненту связности. Клетки, покрашенные в цвет с номером \(1\), имеют координаты \((1, 0)\) и \((2, 0)\) и поэтому также образуют \(1\) компоненту связности. Несложно увидеть, что все остальные условия тоже выполнены.
В третьем тестовом примере количество клеток с каждым значением, кроме \(0\) и \(7\), равняется \(1\). Количество клеток с \(7\) равняется \(6\), что подходит под интервал \([1, 20]\), и на количество клеток с \(0\) в условии не накладывается ограничений. Каждый цвет образует \(1\) компоненту связности, так как все клетки инцидентны к первому ряду, который связан по всем цветам.
1
2 2 0 1 1 1
2
3 3 0 3 1 3 3 3 2 3 3
3
5 5 0 1 6 2 3 1 1 7 3 3 6 7 6 6 7 4 5 6 6 7 5 5 7 7 7