CF228B.Two Tables
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You've got two rectangular tables with sizes n__a × m__a and n__b × m__b cells. The tables consist of zeroes and ones. We will consider the rows and columns of both tables indexed starting from 1. Then we will define the element of the first table, located at the intersection of the i-th row and the j-th column, as a__i, j; we will define the element of the second table, located at the intersection of the i-th row and the j-th column, as b__i, j.
We will call the pair of integers (x, y) a shift of the second table relative to the first one. We'll call the overlap factor of the shift (x, y) value:

where the variables i, j take only such values, in which the expression a__i, j·b__i + x, j + y makes sense. More formally, inequalities 1 ≤ i ≤ n__a, 1 ≤ j ≤ m__a, 1 ≤ i + x ≤ n__b, 1 ≤ j + y ≤ m__b must hold. If there are no values of variables i, j, that satisfy the given inequalities, the value of the sum is considered equal to 0.
Your task is to find the shift with the maximum overlap factor among all possible shifts.
你有两张矩形表格,尺寸分别为 na×ma 和 nb×mb 个单元格。表格中仅包含数字 0 和 1。我们将两张表格的行与列均从 1 开始编号。设第一张表格中第 i 行、第 j 列位置的元素为 ai,j;第二张表格中第 i 行、第 j 列位置的元素为 bi,j。
我们称整数对 (x,y) 为第二张表格相对于第一张表格的一个偏移量(shift)。该偏移量 (x,y) 的重叠因子(overlap factor)定义为:

其中变量 i,j 仅取使表达式 ai,j⋅bi+x,j+y 有意义的值。更严格地说,需同时满足以下不等式:
1≤i≤na,1≤j≤ma,1≤i+x≤nb,1≤j+y≤mb.
若不存在满足上述不等式的 i,j 取值,则该求和式的值视为 0。
你的任务是:在所有可能的偏移量 (x,y) 中,找出重叠因子最大的那个偏移量。
输入格式
The first line contains two space-separated integers n__a, m__a (1 ≤ n__a, m__a ≤ 50) — the number of rows and columns in the first table. Then n__a lines contain m__a characters each — the elements of the first table. Each character is either a "0", or a "1".
The next line contains two space-separated integers n__b, m__b (1 ≤ n__b, m__b ≤ 50) — the number of rows and columns in the second table. Then follow the elements of the second table in the format, similar to the first table.
It is guaranteed that the first table has at least one number "1". It is guaranteed that the second table has at least one number "1".
第一行包含两个以空格分隔的整数 na、ma(1≤na,ma≤50),分别表示第一个表格的行数和列数。接下来 na 行,每行包含 ma 个字符,表示第一个表格的元素。每个字符为 "0" 或 "1"。
下一行包含两个以空格分隔的整数 nb、mb(1≤nb,mb≤50),分别表示第二个表格的行数和列数。随后按与第一个表格相同的格式给出第二个表格的元素。
保证第一个表格中至少有一个数字 "1"。
保证第二个表格中至少有一个数字 "1"。
输出格式
Print two space-separated integers x, y (|x|, |y| ≤ 109) — a shift with maximum overlap factor. If there are multiple solutions, print any of them.
输出两个以空格分隔的整数 x、y(满足 ∣x∣,∣y∣≤109)——使得平移后的重叠因子最大。若存在多个解,输出任意一个即可。
输入输出样例
输入#1
3 2 01 10 00 2 3 001 111
输出#1
0 1
输入#2
3 3 000 010 000 1 1 1
输出#2
-1 -1
输入解题思路,AI测评打分。不知道怎么写?