- Описание
- Отправленные решения
6. Шоу воздушных шаров
Художник N создал перформанс управляемых миниатюрных воздушных шаров. Они парят в ночном небе в виде квадрата $N \times N$ и светятся. С помощью нейросети художник сгенерировал палитру из $N^2$ цветов в формате OKLCH и присвоил каждому цвету порядковый номер. Полученная палитра обладает следующим свойством: пара цветов с порядковыми номерами $i$, $j$ считается красивой, если $i < j$. Путь из шаров в квадрате считается красивым, если цвета всех соседних пар шаров красивы, а последний шар находится на краю квадрата. В качестве соседей шара учитываются только вертикальные и горизонтальные шары, но не диагональные.
Необходимо написать программу, которая в заданной случайной расстановке найдёт количество воздушных шаров в самом длинном красивом пути, а также количество таких путей.
Формат ввода
В первой строке вводится число $N \le 100$ — размер матрицы. В следующих $N$ строках находится $N$ чисел, разделённых пробелом, — порядковые номера цветов шаров.
Формат вывода
В ответе выведите два числа через пробел: количество шаров в самом длинном красивом пути и количество таких путей.
Примечание
В условии из примера 1 существует 8 красивых путей длины 5:
1 2 4 5 9
1 3 4 5 9
1 2 4 6 9
1 3 4 6 9
1 2 4 6 7
1 3 4 6 7
1 2 4 5 8
1 3 4 5 8
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
3
1 2 7
3 4 6
8 5 9
5 8
Пример 2
4
4 5 11 14
7 12 13 3
2 10 6 8
1 9 16 15
4 3
Пример 3
6
36 35 34 33 32 31
17 16 15 14 13 30
18 5 4 3 12 29
19 6 1 2 11 28
20 7 8 9 10 27
21 22 23 24 25 26
36 1