- Описание
- Отправленные решения
463. Фруктовая радуга
Фуд-стилист и художник Оранж создал картину, используя фрукты разных цветов. Картина создана в виде квадрата $N \times N$. С помощью нейросети художник сгенерировал палитру из $N^2$ цветов в формате OKLCH и присвоил каждому цвету порядковый номер. Полученная палитра обладает следующим свойством: пара цветов с порядковыми номерами $i$, $j$ считается красивой, если $i < j$. Путь из фруктов в квадрате считается красивым, если цвета всех соседних пар фруктов красивы, а последний фрукт находится на краю квадрата. В качестве соседей фрукта учитываются только вертикальные и горизонтальные фрукты, но не диагональные.
Необходимо написать программу, которая в заданной случайной расстановке найдёт количество фруктов в самом длинном красивом пути, а также количество таких путей.
Формат ввода
В первой строке вводится число $N$ $(1 \le N \le 100)$ — размер матрицы.
В следующих $N$ строках находится $N$ чисел $A_{i,j}$ $(1 \le A_{i, j} \le N^2)$, разделённых пробелом, — порядковые номера цветов фруктов.
Гарантируется, что все порядковые номера различны.
Формат вывода
В ответе выведите два числа через пробел: количество фруктов в самом длинном красивом пути и количество таких путей.
Примечание
В условии из Примера 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