Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: N-dimension Matching
Description Let us consider an n-dimension matching problem of two matrices. Here the index number of each dimension of a matrix starts at 1. For two n-dimension matrixes S and T, if there is a position (p _{1}, p_{2}, p_{3}, p_{4}, …,p_{n}) which satisfies that each element at the position (t_{1}, t_{2}, t_{3}, t_{4}, …,t_{n}) in T is the same as the element at the position (p_{1} + t_{1} - 1, p_{2} + t_{2} - 1, p_{3} + t_{3} - 1, p_{4} + t_{4} - 1, …,p_{n} + t_{n} - 1) in S, we call it’s a matching position. So the n-dimension problem is to compute the matching position for given S and T. You can assume that the traditional string matching problem is the 1-dimension version of this problem, and the normal matrix matching problem is the 2-dimension version.Input The first line contains the positive number n, which is not larger than 10.
The second line contains n positive numbers a _{1}, a_{2}, a_{3}, ...,a_{n}, representing the range of each dimension of matrix S.
The third line contains n positive numbers b _{1}, b_{2}, b_{3}, ...,b_{n}, representing the range of dimensions of matrix T.
The fourth line gives the elements in S. The fifth line gives the elements in T. To give out an n-dimension matrix with size c _{1} * c_{2} * c_{3} * ... * c_{n} in a line, we will give the element at the position (d_{1}, d_{2}, d_{3}, …,d_{n}) in the matrix as the (c_{2} * c_{3} * ... * c_{n} * (d_{1} – 1) + c_{3} * c_{4} * ... * c_{n} * (d_{2} – 1) + ... + c_{n} * (d_{n - 1} – 1) + d_{n})–th element in the line.
We guarantee that b _{i} <= a_{i}, elements in S and T are all positive integers that are not larger 100, and the number of the elements in S and T are both not larger than 500000.
Output You should output n numbers in a line, p _{1}, p_{2}, p_{3}, …,p_{n}, representing the matching position. Please print the lexically smallest one if there are many. We guarantee that there is at least one matching position.Sample Input 2 4 4 2 2 3 2 1 1 2 2 2 1 1 2 2 2 1 1 2 2 2 2 2 2 Sample Output 2 2 Source POJ Monthly--2006.06.25, Long Fan |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator