Входные данные: code.in Выходные данные: code.out Время на тест: 5 секунд Тесты к задаче:Скачать Автор задачи: Данченко А.Н.
Секретные службы Ламерлэнда перехватили важное сообщение, хранящееся в закодированном виде. Оно представляет собой прямоугольную матрицу, состоящую из нулей и единиц. Известно, что часть ключа, с помощью которого можно расшифровать сообщение, находится в самой матрице. Также была перехвачена вторая часть ключа, назовем ее образцом, по которой можно найти первую. Эта часть ключа также представляет собой прямоугольную матрицу из нулей и единиц.
Для того чтобы восстановить ключ полностью, необходимо найти ячейку в сообщении с наибольшим коэффициентом схожести. Если таких ячеек несколько, то, найдя любую из них, мы сможем расшифровать сообщение. Коэффициент ячейки находится по следующим правилам.
Вырежем из сообщения матрицу, у которой размеры равны размерам образца, а левый верхний угол - исследуемая ячейка. Теперь, каждый столбец образца поэлементно сравним с соответствующим столбцом полученной матрицы. Будем подсчитывать количество найденных отличий элементов. Если существует не более одного отличия, то столбец считаем подходящим. Подсчитаем количество подходящих столбцов нашей матрицы. Это число назовем коэффициентом схожести исследуемой ячейки.
Например, если сообщение имеет следующий вид:
1
0
1
0
1
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
а образец:
0
1
0
1
1
1
0
1
0
то наибольший коэффициент будет равен 3, и ячейка с таким коэффициентом будет находиться во второй строке, в третьем столбце.
Требуется составить программу, которая по сообщению и образцу найдет позицию ячейки с максимальным коэффициентом схожести. Если таких ячеек существует несколько, то требуется вывести любую из них.
Формат ввода.
В первой строке входного файла code.in находятся n1 и m1 - размеры образца. Затем следуют n1 строк, в каждой из которых через пробел находятся ровно m1 чисел, равных единице или нулю, описывающих очередную строку образца. В следующей строке находятся n и m - размеры сообщения. В последующих n строках через пробел находятся ровно по m чисел, равных единице или нулю, описывающих строки сообщения.
Ограничения.
Все числа на вводе целые.
0<n,m<1001
0<n1,m1<17
n1<=n, m1<=m
Формат вывода.
В первой строке выходного файла code.out должно находится число - максимальный коэффициент схожести. Во второй строке находятся два числа, разделенные пробелом - координаты ячейки с максимальным коэффициентом.