A beetle is jumping on a checkerboard of size N X N squares. Each square has coordinates, a pair of integers (i,j), where i is the row number and j is the column number.Associated with each square is the coordinates of the square it jumps to when it lands there. For example, in the 6 X 6 checkerboard below, the beetle jumps to (2,3) from (1,1), and jumps to (5,2) from (6,4)
If the starting location is given, the objective is to determine the position of the beetle after a large number of jumps.
Input
The first line of the input has three comma separated positive integers N,P,Q. N is the length of a side of the checkerboard (the checkerboard is of size N X N). The number of jumps the beetle makes is PQ (P multiplied by Q)
The next N lines consist of N pairs of comma separated positive integers, each pair separated by a semicolon(;). The mth pair in line k represents the coordinates of the square it jumps to if it lands on square (k,m).
Finally, there is one line with a comma separated pair of numbers giving the initial position of the beetle
Output
The output is the coordinates of the beetle’s position after PQ moves
Constraints
6<=N<=20
1<=P,Q<10^9
Example 1
Input:
6,2,3
2,3;2,4;2,1;3,5;3,4;4,2
4,2;4,1;3,1;3,6;4,4;1,4
1,2;1,3;4,5;5,5;2,1;1,5
6,2;6,1;2,2;5,6;2,6;2,5
3,2;3,3;6,5;6,6;6,3;6,4
5,3;5,4;5,1;5,2;4,6;1,6
1,2
Output:
6,3
Explanation:
N is 6, P is 2
and Q is 3. The size of the checkerboard is 6 X 6. The next 6 lines give the
“jump to” coordinates if the beetle is
on the
corresponding square. The starting position of the beetle is (1,2)
The checkerboard
is the same as pictured above. The output should be the position of the beetle
after (2)(3)=6 moves. The
position after each of the moves is (2,4);(3,6);(1,5);(3,4);(5,5);(6,3). Hence the output is 6,3
Example 2
Input:
6,12,2
2,3;2,4;2,1;3,5;3,4;4,2
4,2;4,1;3,1;3,6;4,4;1,4
1,2;1,3;4,5;5,5;2,1;1,5
6,2;6,1;2,2;5,6;2,6;2,5
3,2;3,3;6,5;6,6;6,3;6,4
5,3;5,4;5,1;5,2;4,6;1,6
4,3
Output:
6,1
Explanation:
N is 6, P is 12
and Q is 2. The checkerboard is 6 X 6. The output must be the coordinates after
(12)(2)=24 moves. The next 6
lines show that
the checkerboard is the same as pictured above. The starting position is (4,3)
The first 24
moves are (2,2)… (1,2);(4,2);(6,1). Hence, the output is 6,1
0 Comments