Codeforces Round 531 (Div. 3) |
---|
Закончено |
Задана матрица $$$a$$$, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. В каждой ячейке записано целое число.
Разрешается произвольно изменить порядок строк (в том числе и оставить начальный порядок), но не разрешается менять порядок ячеек в строке. После того, как был выбран некоторый порядок строк, матрица полностью обходится следующим образом: сначала посещаются все ячейки первого столбца с верхней строки до нижней, потом так же все ячейки второго столбца и так далее. Во время обхода выписывается последовательность чисел в ячейках в том же порядке, в котором они были посещены. Назовем эту последовательность $$$s_1, s_2, \dots, s_{nm}$$$.
Обход называется $$$k$$$-приемлемым, если для всех $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| \ge k$$$.
Найдите такое максимальное целое число $$$k$$$ такое, что существует порядок строк матрицы $$$a$$$, который образует $$$k$$$-приемлемый обход.
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 16$$$, $$$1 \le m \le 10^4$$$, $$$2 \le nm$$$) — количество строк и столбцов, соответственно.
В каждой из следующих $$$n$$$ строк записаны по $$$m$$$ целых чисел ($$$1 \le a_{i, j} \le 10^9$$$) — описание матрицы.
Выведите единственное целое число $$$k$$$ — такое максимальное число, что существует порядок строк матрицы $$$a$$$, который образует $$$k$$$-приемлемый обход.
4 2 9 9 10 8 5 3 4 3
5
2 4 1 2 3 4 10 3 7 3
0
6 1 3 6 2 5 1 4
3
В первом примере можно переставить строки следующим образом, чтобы получить $$$5$$$-приемлемый обход:
5 3
10 8
4 3
9 9
Тогда последовательность $$$s$$$ будет $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$. Каждая пара соседних элементов отличается хотя бы на $$$k = 5$$$.
Во втором примере максимальное $$$k = 0$$$, любой порядок $$$0$$$-приемлем.
В третьем примере заданный порядок уже $$$3$$$-премлемый, можно его оставить.
Название |
---|