Задача №3395. Снова в космос
К 50-летию первого пилотируемого полета в космос решено создать новый тип космического корабля многоразового использования “Восторг”. Прямоугольная часть его корпуса (далее прямоугольник) должна быть облицована квадратными термозащитными плитками разных цветов одного и того же размера. Прямоугольник состоит из \(r\) рядов по \(c\) плиток в каждом. Плитки должны образовывать заданный рисунок.
Облицовка космического корабля отдельными плитками очень трудоемка, поэтому для выкладывания заданного рисунка используются одинаковые прямоугольные панели, состоящие из плиток. Панели крепятся на корпусе одна за другой, заполняя ряд за рядом сверху вниз. Каждый ряд панелей может быть сдвинут относительно предыдущего на одно и то же число плиток. При этом панели могут выходить за пределы прямоугольника. Панели должны быть одинаково ориентированы, то есть при параллельном переносе одной панели на место другой цвета образующих эти панели плиток должны совпадать.
Главный конструктор хочет выбрать такой размер панели \(a\times b\) и сдвиг \(s\), чтобы этими панелями можно было выложить заданный рисунок, и площадь панели была минимальна.
Пример панелей с \(a = 2\), \(b = 3\), \(s = 1\).
Требуется написать программу, которая по заданному расположению плиток в прямоугольнике рассчитывает размеры минимальной по площади панели, которую можно использовать при его облицовке, а также величину сдвига вправо (\(0 \leq s < b\)) каждого следующего ряда относительно предыдущего.
Первая строка входного файла содержит два целых числа: \(r\) и \(c\) – размеры прямоугольника в плитках. В последующих \(r\) строках указаны цвета плиток фрагмента. Каждый из \(k \leq 26\) цветов обозначен одной из первых \(k\) прописных букв латинского алфавита. Гарантируется, что для этого прямоугольника можно подобрать панель размера \(a\times b\), такую, что \(2a \leq r\) и \(2b \leq c\).
ВВ выходной файл необходимо вывести три целых числа \(a\), \(b\) и \(s\), удовлетворяющих условиям задачи. Если решений несколько, разрешается вывести любое из них.
Во втором примере облицовка прямоугольника соответствуют следующему рисунку (выступающие за границы прямоугольника части панелей не показаны):
Данная задача содержит семь подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 20.
В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 200.
В правильном ответе величина сдвига \(s\) равна нулю, \(r\) и \(c\) не превосходят 1961.
Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 20.
Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 200.
Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 500.
Величина сдвига \(s\) произвольна, \(r\) и \(c\) не превосходят 1961.
2 4 ABAB ABAB
1 2 0
5 7 DCADCAD BABBABB ADCADCA BBABBAB CADCADC
2 3 1