Untitled
unknown
plain_text
2 years ago
39 kB
10
Indexable
Path finding puzzles
Write a program to read in and solve path-finding puzzles. Each puzzle consists of an NxN array of integers, like this:
//Ben duoi la hinh 10x10
7
4
4
6
6
3
2
2
6
8
3
3
6
5
4
3
7
2
8
3
4
1
6
6
2
4
4
4
7
4
4
5
3
4
3
5
4
4
8
5
5
1
4
6
6
5
0
7
1
4
2
6
9
4
9
7
7
9
1
4
3
5
4
0
6
4
5
5
5
6
6
6
2
3
4
7
1
2
3
3
3
5
4
3
6
5
4
5
2
6
3
9
3
5
1
1
5
4
6
6
The problem is as follows: Starting in the upper left-hand corner (location [0][0]), find a sequence of moves that takes you to the bottom right-hand corner (for an NxN array, this would be location [N-1][N-1]). From each location in the array you may move left, right, up, or down; the number in the location tells you exactly how far to move.
For example, location [0][0] contains a 7, so from there you must move exactly 7 squares, either to the right or down. You cannot move up or left, because that would take you outside the array.
To help you see the solution, the squares along the solution path have been colored orange. From 7 you move right to 2, down to 4, down to 5, up to 5, etc. The complete solution is
[(0, 0), (0, 7), (2, 7), (6, 7), (1, 7), (1, 5), (1, 2),
(7, 2), (7, 4), (7, 8), (4, 8), (5, 8), (5, 9), (9, 9)].
(Also, in the example, there are several squares from which you cannot move at all! Can you find them?)
Input
The first line contains t, the number of test cases followed by a blank space. Each of the t tests start with a number n (n <= 20). Then n + 1 lines follow. In the ith line a number A[i - 1] is given. The (n + 1)th line is a blank space.
Output
If you can reach the destination, print 'YES', otherwise print 'NO'.
Sample
Input
2
8 1 8 6 1 2 5 3 7 9
6 0 3 1 3 8 7 0 4 6
7 4 6 2 2 4 3 9 8 3
7 1 4 0 4 2 3 1 6 6
1 9 4 6 2 4 2 2 3 4
9 5 4 2 5 0 4 8 3 3
3 0 4 3 7 7 5 4 4 4
5 6 8 9 3 7 1 2 9 0
4 0 3 1 0 5 0 5 6 6
9 7 6 5 5 5 3 9 2 2
10
6 4 4 4 1 8 1 5 2 9
0 5 7 2 8 8 0 3 3 5
9 7 8 0 7 2 3 9 5 6
6 6 2 4 6 4 1 3 2 1
4 4 2 0 5 9 7 7 3 3
9 2 7 2 9 1 7 6 0 9
6 3 5 0 8 2 4 2 0 7
5 3 1 5 4 9 3 0 6 7
0 4 2 6 9 8 1 3 6 3
3 2 3 0 0 3 8 1 8 5
Output
YES
YES
//test case
21
10
8 1 8 6 1 2 5 3 7 9
6 0 3 1 3 8 7 0 4 6
7 4 6 2 2 4 3 9 8 3
7 1 4 0 4 2 3 1 6 6
1 9 4 6 2 4 2 2 3 4
9 5 4 2 5 0 4 8 3 3
3 0 4 3 7 7 5 4 4 4
5 6 8 9 3 7 1 2 9 0
4 0 3 1 0 5 0 5 6 6
9 7 6 5 5 5 3 9 2 2
10
6 4 4 4 1 8 1 5 2 9
0 5 7 2 8 8 0 3 3 5
9 7 8 0 7 2 3 9 5 6
6 6 2 4 6 4 1 3 2 1
4 4 2 0 5 9 7 7 3 3
9 2 7 2 9 1 7 6 0 9
6 3 5 0 8 2 4 2 0 7
5 3 1 5 4 9 3 0 6 7
0 4 2 6 9 8 1 3 6 3
3 2 3 0 0 3 8 1 8 5
10
3 5 2 3 3 3 4 8 9 2
8 6 7 6 4 4 8 0 4 2
3 5 9 8 4 0 3 3 2 9
1 9 2 9 7 9 7 2 2 8
5 1 2 0 5 0 2 8 2 6
0 9 0 4 8 6 3 9 6 0
8 2 5 3 9 4 1 7 4 1
3 9 7 1 1 6 2 4 2 3
1 6 7 0 8 0 6 9 3 4
9 7 1 7 4 8 3 2 4 4
10
7 4 4 5 0 6 0 5 0 6
5 9 7 6 1 1 8 9 4 3
5 7 0 4 9 2 0 0 1 3
4 8 5 6 0 8 9 0 8 0
8 6 9 4 7 6 1 7 8 8
0 9 2 0 3 6 5 3 8 3
5 7 9 7 8 8 2 2 4 9
9 9 5 5 3 5 7 0 4 3
6 3 4 3 6 1 6 6 0 3
5 4 7 8 4 4 6 9 5 9
10
6 7 7 7 8 2 8 5 4 8
1 7 3 5 2 7 8 7 8 5
9 4 0 7 2 5 0 8 1 2
0 0 9 6 6 2 1 7 8 2
3 5 2 7 3 6 1 0 0 0
6 0 8 0 9 3 5 5 0 8
9 8 8 6 7 0 3 6 1 8
4 6 5 5 9 3 6 1 2 2
3 6 1 3 0 4 7 1 0 5
4 8 1 6 1 5 6 2 2 6
10
2 9 1 2 2 6 7 5 2 2
7 1 3 1 7 7 5 2 2 3
9 4 6 0 2 0 4 0 5 9
2 6 4 9 4 3 6 4 9 3
1 8 5 4 3 5 1 7 3 8
3 9 8 7 2 7 3 4 6 0
5 3 6 2 4 0 8 0 2 8
4 5 2 8 6 1 4 6 9 0
7 8 0 5 1 7 4 3 8 6
4 9 3 5 3 0 2 8 0 9
10
1 2 5 5 0 8 5 4 5 6
7 6 7 1 1 5 1 2 7 6
8 4 9 5 1 6 3 8 5 5
7 5 8 4 3 4 7 1 0 0
2 6 6 2 7 1 2 1 4 9
6 0 7 4 1 6 8 5 9 5
9 8 1 5 1 9 9 6 2 9
3 4 0 9 2 9 6 0 6 3
5 7 9 5 0 3 2 7 5 5
8 9 4 8 0 9 1 4 3 3
10
3 9 8 6 7 5 6 9 0 9
9 8 3 5 2 4 6 8 9 0
5 9 0 5 0 2 5 0 3 1
6 4 0 3 3 8 8 8 7 6
4 4 0 9 5 2 6 6 6 5
4 2 2 3 2 0 4 9 4 3
7 4 2 3 4 0 8 0 6 8
3 6 1 4 7 1 8 8 7 1
5 3 9 2 3 7 5 0 4 9
0 1 1 0 1 5 6 5 7 6
10
1 6 2 9 4 0 8 2 2 1
8 4 9 7 5 7 3 9 1 4
9 8 0 7 5 7 3 5 3 8
9 7 4 0 5 1 3 1 1 6
2 3 5 1 4 4 3 6 8 5
2 4 9 1 2 6 8 5 3 1
1 4 3 2 0 1 9 1 4 3
9 8 7 1 7 7 2 5 2 6
9 8 7 4 1 3 2 6 6 8
9 8 3 7 7 4 0 0 1 6
10
4 7 4 7 9 0 8 9 5 1
7 3 3 8 7 8 2 0 1 1
9 4 3 1 2 9 0 9 7 7
1 9 6 5 7 5 4 3 2 2
4 5 6 0 7 5 8 2 5 7
4 1 8 1 4 3 1 6 2 8
5 3 7 5 2 3 8 2 7 8
5 0 2 0 7 6 3 7 8 5
4 8 2 6 0 4 3 5 1 4
3 1 2 3 3 6 6 6 1 5
10
3 5 0 0 7 7 3 1 7 6
0 2 2 6 1 9 9 5 3 0
0 4 3 4 3 6 9 7 3 5
3 0 7 7 9 1 4 6 7 8
4 0 1 4 7 6 6 7 1 0
1 6 1 0 6 6 2 4 9 1
5 3 9 3 7 7 5 4 6 0
1 2 6 0 4 1 2 7 6 6
0 8 8 4 2 0 9 9 0 7
9 5 1 3 4 8 5 3 5 4
20
7 9 1 17 6 8 18 19 12 18 5 19 15 6 9 3 13 9 14 11
18 19 10 18 11 12 3 5 14 4 14 11 17 6 6 8 6 17 7 18
19 16 11 13 11 4 14 17 6 1 14 4 15 3 14 11 17 1 6 18
8 17 5 13 14 11 9 15 0 6 1 15 5 9 6 2 12 13 19 9
4 8 3 7 19 5 4 19 0 19 1 7 10 11 13 8 14 1 19 12
16 3 5 13 10 13 9 17 13 15 0 15 9 0 7 14 6 17 4 17
10 1 3 4 12 1 6 3 17 1 14 13 19 13 3 16 8 14 6 4
8 0 11 3 12 0 1 0 9 1 15 12 3 0 8 9 11 10 12 3
17 15 3 6 18 0 2 2 12 9 10 10 11 11 7 1 5 5 2 6
14 12 15 13 15 6 10 2 12 2 10 3 6 17 2 1 18 8 14 0
13 5 17 11 5 11 14 17 17 12 17 19 12 0 1 10 6 6 7 11
8 1 8 9 2 12 18 8 3 7 8 19 12 1 17 18 10 1 13 4
11 17 7 3 14 8 17 19 14 17 6 2 7 7 9 9 3 17 9 16
4 12 15 16 13 18 13 19 6 15 6 14 5 1 1 1 7 16 13 10
11 2 8 13 9 14 5 18 17 8 18 13 8 3 6 14 7 9 10 16
0 2 9 3 8 14 8 19 13 4 3 17 2 2 1 13 1 16 3 4
8 6 18 5 3 6 19 11 7 1 14 10 16 14 19 18 17 12 12 14
8 8 16 4 6 14 18 7 6 6 8 1 2 2 18 15 3 8 17 17
18 1 9 6 6 19 2 6 9 17 6 15 5 5 7 11 7 4 12 9
12 6 6 15 3 5 8 12 9 6 7 12 9 5 18 4 14 8 14 2
20
4 15 4 3 18 4 15 12 8 14 15 11 1 7 9 15 8 6 14 11
5 16 16 8 15 19 1 18 4 0 16 11 13 0 9 16 10 10 3 6
15 7 19 3 4 13 8 14 18 4 11 6 1 17 15 13 2 6 13 9
11 16 19 13 11 14 10 8 10 8 6 1 7 8 2 5 5 10 12 17
3 19 14 2 9 17 5 15 17 9 0 5 2 6 11 7 2 14 7 19
1 3 0 9 17 6 13 18 13 10 6 6 9 11 10 16 4 3 16 16
8 19 19 13 12 5 17 12 11 3 16 5 6 17 9 17 5 13 19 8
2 14 3 7 13 16 9 1 9 0 15 6 3 11 6 4 10 3 19 13
6 7 2 2 14 7 2 6 6 18 1 11 12 13 4 15 0 17 7 6
4 5 6 11 2 10 9 11 9 17 14 9 18 15 3 1 2 0 15 8
8 1 5 9 3 19 2 15 10 12 5 12 19 3 0 6 5 18 7 6
8 10 15 17 6 6 16 10 3 8 16 4 4 3 1 4 9 13 8 15
9 3 7 1 18 8 18 13 15 15 12 9 1 18 12 0 6 19 5 3
3 8 1 19 8 3 7 0 19 12 13 18 13 5 0 16 5 9 13 1
14 14 19 5 2 7 18 16 14 3 0 2 11 4 1 14 2 4 18 19
2 9 11 19 18 18 4 12 5 18 12 8 8 2 11 2 4 11 9 10
11 12 12 13 9 3 8 2 3 3 18 13 13 17 19 12 7 12 6 18
3 15 17 13 1 13 17 18 18 1 3 1 17 8 0 16 12 15 16 6
10 9 7 1 2 7 3 3 14 17 16 16 14 14 17 13 1 16 16 3
12 17 4 16 13 8 18 15 9 14 10 10 14 8 17 13 5 15 17 6
20
7 0 13 8 0 8 10 14 12 6 14 2 1 10 3 8 1 2 3 11
13 18 0 6 19 4 11 13 3 14 9 14 7 16 3 18 18 10 3 7
11 19 10 3 7 5 4 5 5 19 5 1 10 12 14 7 9 9 9 17
11 18 16 7 17 11 6 13 19 17 11 10 4 4 12 0 0 2 1 14
4 19 8 6 10 16 2 1 14 1 18 16 16 11 10 16 0 4 15 14
15 5 12 14 12 14 13 13 5 15 10 2 18 17 12 18 12 1 13 1
19 18 7 11 0 9 9 17 5 8 18 15 12 18 3 9 18 2 19 3
12 0 14 19 0 0 14 12 5 3 15 1 0 16 17 1 9 13 16 7
2 6 10 2 5 6 8 5 14 8 3 15 13 15 11 18 11 3 11 6
13 8 15 2 14 2 10 1 3 4 13 17 12 3 16 7 15 3 8 14
4 16 14 13 19 11 17 12 8 4 5 8 19 18 18 16 13 0 7 3
12 6 7 15 16 18 17 7 17 11 8 3 6 16 2 4 5 15 5 9
17 0 10 6 2 7 15 11 15 17 10 17 13 12 4 14 15 10 1 13
9 2 17 17 0 5 11 4 17 19 1 14 12 6 10 6 13 18 0 13
13 12 16 14 15 17 18 3 12 10 2 5 2 13 15 16 1 5 10 15
6 10 17 12 13 7 7 13 10 1 5 16 14 18 6 4 18 5 7 13
14 0 19 0 16 10 1 0 2 16 14 0 5 17 8 14 18 12 1 0
5 17 17 2 16 14 0 0 8 11 19 18 6 13 7 17 10 14 15 11
18 2 1 3 0 2 4 4 10 14 13 0 5 9 10 17 6 13 4 5
1 19 4 1 8 10 10 8 17 2 19 0 6 8 6 18 4 7 12 14
20
17 0 10 2 5 5 5 10 14 12 10 1 2 17 15 11 13 19 14 10
18 10 12 2 6 0 6 7 10 3 11 19 3 10 7 13 17 12 1 4
9 12 3 1 17 12 14 16 13 11 17 16 3 15 8 9 3 4 19 9
17 17 18 15 15 12 0 8 4 7 3 2 7 15 3 14 16 11 10 13
8 15 9 14 9 16 5 15 17 14 17 3 15 13 2 2 2 18 6 0
6 6 12 19 18 8 12 18 16 15 2 14 16 3 8 11 15 7 8 10
13 10 2 2 18 11 19 18 15 5 9 15 5 1 6 14 14 13 4 14
13 15 9 15 4 3 4 17 1 15 10 6 3 12 18 3 0 11 10 0
6 4 17 7 9 6 15 7 10 9 5 10 16 3 14 17 2 9 7 5
15 1 15 6 16 17 17 9 12 1 2 1 19 10 12 4 15 17 15 12
16 0 2 17 1 17 11 5 5 11 16 0 14 1 0 4 12 15 3 9
11 6 1 7 9 17 10 7 14 7 6 12 7 2 12 9 19 10 2 4
17 10 15 17 19 18 17 7 18 3 19 6 5 10 13 5 18 12 9 0
14 7 18 14 2 12 4 9 12 15 8 6 12 17 8 8 3 16 3 6
15 18 18 13 5 6 17 3 6 16 19 18 1 18 19 4 9 7 7 18
14 9 16 3 12 6 4 8 5 9 10 19 7 6 13 15 16 8 15 8
17 7 14 9 11 11 14 1 1 17 0 14 3 7 14 19 12 18 19 17
13 2 11 11 0 8 15 8 4 11 10 15 7 15 11 4 1 5 4 8
11 13 4 11 4 6 13 4 14 0 14 6 6 3 6 15 5 14 13 13
13 8 8 4 3 0 16 5 1 3 2 17 0 10 5 6 2 19 1 19
20
0 11 10 17 3 1 14 13 13 5 11 13 6 3 1 17 0 16 7 17
17 14 5 8 3 4 19 7 14 17 0 14 5 3 19 18 14 4 9 19
15 14 12 12 16 15 11 10 16 0 4 0 14 12 3 11 19 10 4 4
1 15 1 8 10 11 17 3 0 10 19 18 15 11 8 2 2 5 9 5
13 14 13 19 3 18 13 2 14 8 11 15 16 19 2 17 7 19 3 2
8 3 6 19 1 7 10 16 0 19 13 12 11 12 4 14 7 3 12 9
3 8 5 7 9 17 17 7 2 15 16 10 2 6 18 10 18 4 3 17
5 5 5 17 14 0 2 3 19 4 0 13 12 0 6 6 12 3 0 14
18 6 15 13 14 5 18 12 6 12 19 4 10 3 13 17 7 3 8 7
9 10 0 1 18 8 4 16 17 9 18 15 12 6 11 0 0 11 1 8
18 2 12 10 5 18 13 8 6 16 6 16 7 1 18 14 17 12 18 12
15 7 0 1 9 0 19 3 5 8 4 10 18 3 19 13 7 4 18 6
13 10 2 0 2 11 7 18 18 2 18 2 9 19 16 10 14 15 10 12
4 1 13 3 12 19 1 4 2 19 16 5 10 16 5 14 19 0 12 3
0 17 11 19 12 13 2 0 3 2 10 11 17 3 10 1 8 2 6 2
12 1 2 0 13 7 13 13 5 16 1 19 1 19 10 7 18 4 14 13
3 11 3 14 13 9 2 17 16 10 13 0 17 17 18 3 3 12 6 15
3 0 2 9 10 4 1 18 6 6 16 5 4 15 12 13 2 7 3 13
11 5 12 19 12 5 3 14 10 3 6 15 10 18 10 10 15 10 18 4
9 9 14 0 6 18 7 5 1 15 12 1 7 2 6 15 8 3 17 14
20
10 0 11 12 18 16 1 13 19 1 6 11 4 12 4 10 8 13 2 12
9 11 16 5 19 12 18 13 13 4 13 17 18 18 10 10 14 10 1 1
14 18 4 10 7 18 0 0 1 11 2 15 11 13 19 8 2 13 12 18
3 5 10 11 11 10 19 12 11 6 18 13 12 1 8 16 6 12 6 19
19 9 19 0 8 2 16 12 3 19 18 15 10 10 1 6 3 5 4 16
6 16 2 18 12 16 14 11 15 1 8 2 3 2 7 0 5 2 3 17
16 14 14 0 10 15 6 16 11 19 6 16 3 10 9 7 17 18 12 4
7 7 3 1 16 3 6 16 7 11 4 19 6 16 2 3 6 6 9 15
12 14 4 8 9 1 10 0 10 7 19 12 15 2 2 5 18 7 11 2
9 19 2 13 10 10 3 16 6 0 19 8 7 19 18 1 11 15 7 4
12 7 14 17 6 4 7 19 9 15 9 10 8 5 14 15 16 14 11 15
6 12 2 7 11 2 5 15 18 13 0 6 13 11 4 19 14 13 10 12
4 3 18 18 13 5 13 17 2 15 19 14 5 0 17 0 12 3 14 13
4 1 5 4 6 16 14 6 9 3 19 19 18 10 5 1 18 10 19 6
5 13 12 10 6 18 7 4 19 1 0 6 14 8 8 13 9 1 4 19
13 17 10 16 7 16 16 15 5 4 11 1 7 7 4 10 11 6 10 13
10 15 17 12 11 12 15 1 7 2 13 10 15 2 11 1 17 3 9 15
2 12 3 12 7 2 4 18 18 10 5 11 5 15 0 14 5 1 5 15
5 0 15 10 17 1 5 5 1 14 13 10 12 2 14 14 11 14 9 13
10 8 10 1 9 18 5 0 18 5 3 11 2 19 6 4 6 13 11 7
20
19 13 5 9 18 10 4 2 6 16 5 11 2 2 3 3 5 14 2 1
18 4 19 8 1 14 16 2 2 13 5 3 18 8 1 14 16 17 4 10
9 10 0 12 5 5 17 1 4 0 6 12 7 1 13 18 17 12 15 8
19 13 8 2 13 4 14 9 11 12 7 0 8 14 9 5 2 8 2 10
6 7 5 4 14 17 8 9 15 14 14 19 13 13 2 13 14 14 6 13
15 2 13 12 14 1 12 16 4 3 11 12 13 6 2 3 10 19 9 16
17 1 16 16 14 12 5 10 14 3 13 5 7 7 15 11 12 3 4 8
13 16 7 7 3 4 11 7 1 7 2 16 7 7 7 11 2 17 6 12
16 14 9 8 19 3 1 6 0 2 12 19 5 17 10 11 12 16 12 4
5 6 4 0 6 13 1 10 3 19 17 11 17 2 17 5 16 19 14 1
7 14 3 3 14 18 15 18 10 14 17 2 13 7 9 14 18 16 4 14
9 16 5 10 2 19 2 0 6 6 8 14 13 9 14 11 5 5 10 8
2 6 1 12 1 10 15 9 2 9 7 12 1 13 3 9 12 0 15 3
7 14 5 10 18 10 2 0 3 10 5 3 13 19 5 5 9 18 19 13
9 4 1 18 19 8 5 17 15 10 16 19 15 15 17 8 8 9 18 8
0 18 12 15 5 10 0 19 16 14 12 14 6 6 9 13 17 16 19 11
14 13 5 4 8 7 13 11 19 10 15 8 12 11 18 18 1 14 9 8
16 14 4 7 19 8 9 11 11 8 5 14 10 6 17 12 1 7 5 8
2 6 9 5 1 16 0 0 16 1 8 3 18 2 16 16 19 14 0 17
1 16 1 8 9 16 14 6 17 14 3 16 6 3 5 13 17 14 2 13
20
8 5 14 8 8 13 4 9 13 14 4 13 5 11 5 15 2 2 9 13
16 0 16 6 17 12 8 18 4 1 3 5 6 2 4 3 18 13 16 14
16 12 9 15 6 15 6 13 10 2 10 14 2 8 7 16 15 16 18 0
16 10 16 14 17 0 3 1 15 18 4 4 8 15 1 3 11 13 11 11
12 1 6 16 2 2 16 8 3 15 1 8 15 15 9 4 9 15 4 16
14 4 10 5 9 18 14 16 7 10 18 13 8 7 13 6 12 12 4 17
9 19 2 17 7 7 15 14 9 18 12 11 16 19 13 19 9 17 8 15
3 13 17 15 5 15 17 8 19 9 14 16 3 14 14 9 9 19 14 4
9 7 12 14 14 8 11 3 13 6 11 16 11 17 9 13 0 0 9 0
9 14 12 11 19 14 18 15 11 16 16 2 11 12 7 8 8 6 7 4
19 1 6 19 19 14 3 4 10 7 14 2 11 9 7 18 11 1 7 15
10 2 8 10 8 19 17 15 17 10 9 7 19 13 14 19 6 3 2 6
10 7 0 14 10 12 9 3 15 19 0 19 11 1 9 7 9 5 5 0
15 13 19 18 18 3 0 11 4 14 13 17 16 2 16 14 6 17 10 3
3 13 6 16 19 2 3 14 3 18 11 12 7 8 9 0 6 6 8 10
14 5 7 1 13 14 7 16 1 15 10 14 6 13 5 14 5 15 7 5
16 1 1 17 2 13 11 2 13 6 2 18 11 15 8 13 7 10 9 1
11 8 15 1 2 15 11 19 3 1 3 0 1 19 17 14 2 9 14 18
5 7 19 16 11 6 10 2 0 2 1 15 1 6 14 13 3 14 1 3
10 10 10 2 10 13 11 10 7 15 18 16 1 1 15 8 14 7 3 16
20
19 4 1 2 8 16 6 8 14 4 17 3 1 1 14 6 15 9 14 6
14 5 0 19 10 10 16 8 1 8 0 4 12 11 4 4 16 4 3 12
6 16 0 5 11 1 8 12 0 11 5 7 9 4 19 17 10 16 19 12
9 14 7 0 12 16 16 18 6 4 8 18 2 9 4 6 14 5 0 1
2 6 6 5 0 8 7 6 17 17 3 4 2 6 11 13 18 19 15 9
18 3 10 12 4 0 15 9 0 4 3 4 2 3 9 15 2 3 13 5
14 0 17 9 4 19 2 9 18 18 1 16 15 14 9 9 9 2 16 8
11 15 4 9 1 4 11 2 7 7 0 17 0 10 11 13 11 17 5 12
13 19 0 16 8 17 1 3 3 13 16 13 15 12 16 15 11 18 2 8
8 11 9 1 1 19 1 1 2 16 16 3 2 4 8 5 11 1 0 4
8 10 11 16 3 12 12 13 2 11 1 14 3 10 11 2 12 14 13 8
17 6 12 4 10 15 2 14 11 13 1 1 15 12 10 12 19 2 11 10
4 11 4 8 7 12 18 2 6 0 4 17 0 6 5 1 14 9 10 11
0 6 7 9 14 18 9 9 10 17 18 13 16 4 1 4 7 7 4 9
11 11 1 5 12 11 0 19 13 13 19 11 17 14 8 5 19 18 6 16
10 4 15 0 1 17 13 8 8 6 9 2 10 19 14 1 8 10 15 17
18 5 14 3 7 4 18 15 6 10 1 3 17 15 8 11 7 6 13 17
15 7 19 18 4 11 8 18 14 19 1 14 12 13 18 14 11 4 13 18
5 0 8 19 3 9 7 12 16 7 18 10 16 18 1 0 19 1 13 1
17 3 9 7 2 14 0 0 4 18 1 2 14 12 17 4 2 12 13 15
20
10 6 18 4 2 10 18 16 2 8 13 9 4 8 3 8 3 8 8 0
7 3 16 3 0 5 15 0 6 13 15 5 8 8 5 11 0 10 2 19
14 1 1 9 3 13 14 4 18 2 16 19 6 10 18 4 7 7 19 18
15 16 14 11 9 11 13 14 18 7 6 10 9 1 13 19 9 6 2 17
11 5 3 0 0 3 5 0 11 10 18 12 13 19 9 13 13 0 18 15
19 6 9 7 10 2 2 3 10 2 12 13 5 2 4 2 1 12 1 4
13 2 19 18 15 15 2 14 11 13 19 16 8 16 15 7 10 16 17 1
10 9 6 17 2 2 4 13 15 6 17 4 14 12 19 18 18 17 3 5
1 3 17 10 17 7 5 13 15 12 17 4 3 11 5 12 16 11 3 15
18 9 9 2 16 11 10 0 15 18 14 5 18 6 1 14 4 6 9 15
13 8 15 8 17 18 17 12 4 1 3 13 15 11 10 13 7 15 7 4
5 11 18 13 19 12 12 2 4 9 5 15 18 3 11 16 8 15 1 1
12 6 8 13 9 18 8 14 11 0 7 13 13 9 0 12 17 4 3 6
8 16 0 18 13 3 10 10 16 16 0 11 13 19 15 3 17 2 16 9
13 6 10 5 9 5 5 16 0 18 12 18 0 17 3 11 4 2 2 3
5 19 4 3 11 12 7 7 1 19 4 2 8 10 14 1 9 14 15 15
1 17 16 9 10 17 17 11 14 11 8 7 15 15 15 17 9 5 4 5
4 4 13 4 14 5 0 13 9 16 8 0 18 9 17 1 18 11 14 15
6 4 6 13 2 6 16 10 8 2 1 3 9 17 12 17 19 3 4 15
15 0 4 3 2 19 17 7 6 16 16 14 7 17 3 15 6 10 11 2
Picking up Jewels
There is a maze that has one entrance and one exit.
Jewels are placed in passages of the maze.
You want to pick up the jewels after getting into the maze through the entrance and before getting out of it through the exit.
You want to get as many jewels as possible, but you don’t want to take the same passage you used once.
When locations of a maze and jewels are given,
find out the greatest number of jewels you can get without taking the same passage twice, and the path taken in this case.
Time limit : 1 sec (Java : 2 sec)
[Input]
There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 )
In each test case,
In the first line, the size of the maze N (1 ≤ N ≤ 10) is given. The maze is N×N square-shaped.
From the second line through N lines, information of the maze is given.
“0” means a passage, “1” means a wall, and “2” means a location of a jewel.
The entrance is located on the upper-most left passage and the exit is located on the lower-most right passage.
There is no case where the path from the entrance to the exit doesn’t exist.
[Output]
Output the greatest number of jewels that can be picked up.
[I/O Example]
Input
2
5
0 0 0 2 0
2 1 0 1 2
0 0 2 2 0
0 1 0 1 2
2 0 0 0 0
6
0 1 2 1 0 0
0 1 0 0 0 1
0 1 2 1 2 1
0 2 0 1 0 2
0 1 0 1 0 1
2 0 2 1 0 0
Output
6
4
//test case
10
6
0 2 0 1 2 0
1 1 0 1 0 1
0 0 2 0 0 2
0 1 1 1 1 2
0 2 0 0 2 2
1 1 1 1 2 2
5
0 0 0 2 0
2 1 0 1 2
0 0 2 2 0
0 1 0 1 2
2 0 0 0 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0
7
0 0 0 2 0 0 0
0 1 1 0 1 1 0
2 1 1 0 1 1 0
0 0 0 2 0 2 2
0 1 1 2 1 1 0
0 1 1 0 1 1 0
2 0 0 2 2 1 0
6
0 2 0 1 2 0
2 1 0 1 0 1
2 2 2 0 0 2
0 1 1 0 1 2
0 2 0 0 2 2
1 1 1 1 2 2
10
0 1 2 2 2 0 2 1 1 0
0 1 0 1 1 1 0 2 2 0
0 2 0 2 0 0 0 1 1 0
2 1 0 1 0 1 0 1 2 0
0 1 1 1 0 1 2 1 1 0
2 1 0 1 0 1 0 1 1 0
0 0 0 0 0 1 0 2 2 0
0 1 0 1 1 1 0 1 2 2
2 1 0 1 1 1 0 1 1 0
0 0 2 0 0 0 0 2 2 0
10
0 0 0 2 0 0 1 0 2 0
0 1 0 1 0 1 1 2 1 0
2 1 0 1 2 1 1 0 1 0
0 0 0 2 0 0 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 2 1 0 1 2 2 1 0
0 1 0 2 0 0 2 1 2 0
0 1 0 1 0 1 2 1 2 0
0 1 0 1 0 1 2 1 1 0
0 0 0 0 0 0 2 1 1 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0
10
0 0 0 2 0 0 1 0 2 0
0 1 0 1 0 1 1 2 1 0
2 1 0 1 2 1 1 0 1 0
0 0 0 2 0 0 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 2 1 0 1 2 2 1 0
0 1 0 2 0 0 2 1 2 0
0 1 0 1 0 1 2 1 2 0
0 1 0 1 0 1 2 1 1 0
0 0 0 0 0 0 2 1 1 0
10
0 1 0 2 0 0 0 2 0 2
0 0 0 1 1 0 1 0 1 2
2 1 2 1 1 0 1 0 1 0
0 1 2 1 1 0 1 0 1 2
0 0 2 0 0 2 0 0 0 0
0 1 2 1 0 1 0 1 1 0
0 1 0 1 2 1 2 2 1 2
2 1 0 1 0 1 0 2 0 0
0 1 0 1 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 0
Advertisement Schedule
A shop need to display the advertisement 3 times a day.
However, they only has 1 electric board to display the advertisement, hence they should select the time to display advertisements so that visitors can watch them as much as possible.
When visitors watch advertisement, they can get points which calculated as below :
1. Three Ads have length L1, L2, L3 and the points a person can get after watched them P1, P2, P3.
2. A visitor can get the point of a Ads only when he/she watch the Ads fully (from beginning to the end of that Ads )
3. When a visitor watch more than one Ads and also get the point for them, only the Ads with highest point will be given to that person.
4. Only one Ads can be displayed on electric board at a time (But the next Ads can be displayed right after the previous one ended)
Given the length of each Ads L1, L2, L3 and the point gained for them P1, P2, P3, the arrival time of each visitor into the shop and the time duration that he/she stay in the shop, write a program to select advertisement display time so that as many points as possible can be given to visitors. Print out the total sum of points that the visitors can get.
Ex: There are 7 visitors go to the shop with the arrival time and staying duration as below
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Arrival Time
2
6
3
7
1
2
1
Time Duration
2
4
3
2
1
1
10
Length
Point(s)
Advertisement 1
1
1
Advertisement 2
2
2
Advertisement 3
3
3
Assuming that Ads1 is displayed at time 2, Ads2 at time 7 and Ad3 at time 3, the visitors will watched the ads as below schedule :
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Ads 1
Watch
-
-
-
-
Watch
Watch
Ads 2
-
Watch
-
Watch
-
-
Watch
Ads 3
-
-
Watch
-
-
-
Watch
(Note that visitor 1 didn't watch Ads3 fully, so the point of Ads3 is not given to him)
The points that each visitor can get from watching Ads is show as below :
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Ads 1
1
-
-
-
-
1
1
Ads 2
-
2
-
2
-
-
2
Ads 3
-
-
3
-
-
-
3
Total 12 Points
1
2
3
2
0
1
3
(Visitor 7 watched all Ads fully, however he can only get the highest of one Ads - which is 3 points of Ads 3)
There are many way to arrange the display time, and the method above give us the maximum sum of points which visitors can get, so the answer in this case is 12.
[Constraints]
- The number of visitors N (1 ≤ N ≤ 50)
- The arrival time Ai, the time duration Di of each visitor and the length of each Ads L1, L2, L3 are given as integers (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)
- Ai + Di ≤ 50
- L1 + L2 + L3 ≤ 50
- The starting time of an Ads : 1 ≤ starting time ≤ 50
- P1, P2, P4 are integers (1 ≤ P1, P2, P3 ≤ 1000)
[Input]
The 1st line given T - the total number of TC (T ≤ 50)
In each TC :
- The 1st line contains N, L1, L2, L3, P1, P2, P3 in this order
- The next N lines : each line gives the arrival time Ai and time duration Di of each visitor
5 // Number of test cases T=5
7 1 2 3 1 2 3 // Test case 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3
2 2 // A1 = 2, D1 = 2
6 4 // ...
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
...
[Output]
Out put the maximum sum of points that visitors can get from watching advertisements.
Case #1
12
Case #2
18
Case #3
17
Case #4
16
Case #5
17998
//test case
50
7 1 2 3 1 2 3
2 2
6 4
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
3 1 2 3 7 6 4
10 1
11 2
13 3
5 2 2 1 2 5 4
2 4
4 6
9 1
14 10
30 15
50 31 4 1 734 134 546
1 39
4 28
9 24
12 16
7 29
6 27
12 14
24 18
1 34
11 20
5 23
31 16
12 38
3 35
10 2
35 14
11 34
31 13
6 14
10 7
4 17
15 19
7 36
8 19
13 20
7 18
27 6
9 5
13 14
2 20
9 12
5 13
34 12
5 20
17 7
18 31
33 6
14 8
4 6
10 38
23 10
36 13
17 15
27 20
11 21
27 1
31 13
20 16
47 2
19 26
6 3 4 3 12 9 10
1 3
4 4
8 4
7 4
8 3
1 4
6 1 3 1 11 3 11
17 24
28 7
20 30
4 46
16 6
1 47
6 1 5 2 34 30 17
20 10
1 22
13 2
27 8
8 41
16 33
3 2 3 2 38 43 5
19 4
8 33
11 36
1 2 3 1 19 43 38
11 11
14 2 2 1 70 71 44
11 23
8 26
10 36
17 31
30 12
27 8
33 10
3 32
28 2
8 12
22 26
4 21
15 15
1 13
7 6 9 6 23 74 26
1 15
34 12
26 24
25 12
43 6
12 34
2 18
18 4 4 1 26 68 46
33 6
8 16
45 2
42 1
9 23
43 6
11 20
34 1
23 2
14 2
23 19
21 10
8 6
43 7
21 29
6 2
17 1
30 12
20 5 3 6 14 24 41
5 36
31 12
2 35
4 15
44 1
2 9
5 39
19 2
28 5
25 21
3 28
7 18
1 31
17 9
7 4
4 30
36 7
17 24
1 20
16 3
11 2 3 9 89 39 11
30 2
8 41
13 9
20 9
18 9
23 20
26 11
14 33
8 35
12 35
9 26
7 3 4 10 47 79 87
2 24
1 41
8 1
9 5
24 2
30 1
7 29
7 7 8 8 56 80 39
7 26
35 5
16 28
14 29
16 32
21 18
3 26
12 8 2 9 17 72 28
8 29
4 1
17 24
40 2
21 8
6 9
5 13
17 9
5 39
4 31
28 4
3 36
7 1 8 5 98 57 61
1 4
30 1
27 13
7 11
10 16
21 14
33 9
6 10 5 2 62 3 32
5 21
15 31
10 29
11 15
26 8
5 15
14 12 5 16 145 173 246
29 6
19 28
18 31
33 12
14 30
29 19
33 11
11 16
14 33
6 38
44 5
16 20
18 22
4 38
23 20 6 20 480 471 199
24 23
10 9
9 29
39 6
19 27
24 8
23 12
15 18
23 19
27 8
27 16
14 11
46 3
13 36
4 39
18 19
40 10
16 8
20 28
5 19
26 7
27 13
12 36
21 11 8 12 167 294 326
31 7
19 11
47 3
2 1
4 17
16 12
13 30
14 17
3 44
10 22
24 4
35 8
26 22
19 7
6 30
23 7
32 12
36 8
13 21
24 1
33 7
23 8 3 4 204 177 128
22 14
18 10
7 24
8 21
4 25
14 31
9 34
10 36
6 6
24 18
19 3
39 10
32 3
23 20
20 10
21 20
16 30
20 26
22 17
24 10
14 13
2 10
39 10
15 8 19 11 94 352 337
33 6
8 37
26 3
5 7
29 15
23 2
15 20
26 14
12 23
6 6
25 3
35 13
36 4
15 27
21 1
12 2 16 11 102 320 452
35 14
7 32
3 19
21 26
11 21
24 2
15 10
32 6
38 7
4 31
6 8
10 33
13 2 15 6 194 80 243
13 14
16 2
18 22
13 13
43 6
4 35
30 19
12 17
5 11
7 7
28 18
11 30
4 25
19 5 6 14 138 401 439
45 3
5 5
29 19
23 13
2 7
13 7
11 10
19 1
3 15
37 8
6 11
16 11
19 6
11 32
4 44
10 12
17 13
19 12
6 29
14 2 6 17 201 14 43
18 11
28 13
14 15
12 4
16 9
12 22
4 29
4 15
1 38
24 16
26 17
19 9
31 9
5 21
14 6 11 20 115 187 321
23 24
3 27
12 9
28 18
35 12
6 5
7 5
16 32
1 5
21 11
11 38
36 3
11 23
26 17
29 22 25 1 881 884 274
21 20
23 12
12 16
4 8
6 28
29 8
24 4
1 45
30 12
20 18
29 21
12 36
12 9
15 5
14 15
2 1
30 11
4 27
2 4
31 16
9 17
10 17
45 3
17 14
29 13
17 16
37 2
39 6
30 12
23 13 23 12 498 643 634
8 2
24 1
14 23
2 46
4 46
3 43
7 4
2 13
46 4
2 26
10 20
21 27
9 25
1 25
22 15
10 4
10 25
11 16
5 41
13 12
32 3
35 14
8 31
22 8 21 11 467 961 900
6 23
21 6
36 3
29 6
11 30
17 28
36 14
40 4
24 21
7 37
1 46
2 44
17 12
28 3
34 3
14 18
28 19
11 28
29 10
9 11
1 11
38 4
26 7 20 19 787 304 842
12 7
3 34
27 3
2 48
21 26
7 11
23 22
11 38
24 5
1 41
14 1
4 24
15 21
31 17
5 25
32 12
2 24
12 26
39 5
13 12
36 8
11 9
10 1
6 12
25 11
19 16
34 11 20 16 459 207 689
22 7
23 24
4 34
14 23
23 26
5 21
1 34
13 20
24 11
3 4
10 18
7 28
5 27
16 29
1 24
33 5
16 29
20 11
14 35
11 37
8 3
7 14
41 5
23 3
15 25
29 8
32 3
5 30
6 17
12 31
5 29
44 5
29 20
14 4
31 12 13 22 237 822 823
33 16
25 3
9 34
13 34
25 16
1 45
14 17
15 25
46 4
16 17
10 8
20 4
31 6
33 17
1 31
30 12
7 7
10 5
24 6
13 28
5 3
15 25
2 34
18 9
39 11
7 41
2 46
7 36
23 6
6 36
7 35
33 2 8 25 625 390 641
20 2
18 20
7 1
36 1
30 15
31 13
9 11
43 1
19 24
13 35
8 37
16 9
21 8
19 10
19 14
30 2
6 10
3 19
3 38
30 4
12 21
12 36
22 27
1 2
22 6
41 6
3 20
3 2
16 32
37 3
23 7
4 33
9 15
25 20 4 7 119 439 977
26 1
7 4
21 27
3 16
5 14
15 26
34 10
3 29
15 24
5 13
3 28
33 17
30 13
20 10
20 13
16 28
14 7
1 4
41 3
4 23
30 6
16 30
10 30
19 27
5 39
22 7 2 23 435 733 788
37 2
25 7
15 28
31 5
24 1
32 4
36 5
35 12
31 9
1 23
17 18
32 10
30 14
22 2
1 9
19 23
21 2
31 17
17 31
8 30
41 5
18 27
22 7 12 9 393 913 905
1 16
37 9
21 20
15 13
18 21
5 38
11 14
27 13
14 35
26 17
8 28
19 10
24 12
9 40
5 10
21 1
11 34
19 15
10 30
22 19
24 23
1 23
33 8 32 7 942 106 497
49 1
15 4
6 28
22 19
27 6
10 40
33 5
23 11
20 18
28 15
21 4
5 6
9 15
39 7
21 16
5 34
3 21
28 5
36 1
22 18
17 6
6 16
26 2
39 3
8 19
9 30
12 24
3 9
19 19
36 12
10 1
19 7
28 21
48 1 4 36 965 152 460
27 11
4 26
2 45
23 15
5 26
11 26
2 9
12 29
7 19
13 21
20 8
28 12
12 31
40 2
19 11
18 14
34 8
20 9
32 2
17 33
28 3
36 9
14 35
4 19
3 27
8 7
11 33
10 14
18 22
11 21
11 5
6 36
10 25
26 6
24 24
35 8
15 9
29 12
17 1
11 13
1 6
7 20
16 22
31 8
17 19
34 12
15 25
3 3
43 13 22 9 688 476 169
16 21
11 13
44 5
21 12
26 7
16 24
6 30
36 2
14 32
2 48
9 20
27 5
30 9
11 27
26 13
33 12
7 28
26 19
16 30
3 7
5 17
21 4
2 28
25 21
2 2
11 4
2 48
26 21
9 30
12 2
9 30
4 23
10 19
13 32
26 23
24 14
15 5
4 28
17 11
31 4
4 13
5 17
10 10
37 14 4 15 463 441 250
10 14
36 12
18 28
3 27
7 36
16 16
11 12
24 22
36 6
31 5
9 40
6 10
28 11
43 1
40 5
11 27
25 8
29 3
14 31
2 4
12 23
24 24
33 10
19 11
38 10
32 11
24 10
16 30
42 5
22 16
20 16
3 3
1 5
30 8
8 39
10 22
1 26
31 17 4 4 979 652 689
32 17
26 13
34 16
8 34
24 21
4 12
6 26
4 26
28 8
26 19
7 41
36 8
26 11
32 15
8 9
9 14
37 9
36 5
32 3
27 14
27 3
2 48
8 28
7 25
28 11
26 6
39 9
23 8
39 6
5 40
27 8
50 16 23 2 947 875 329
1 41
35 6
3 28
12 15
28 20
22 21
23 22
35 2
23 15
32 12
10 31
18 8
1 25
22 1
44 6
26 17
18 17
14 21
16 2
17 6
26 20
17 21
45 3
11 31
31 9
21 10
6 23
48 2
10 36
14 29
1 11
34 15
44 3
17 16
9 15
28 17
35 11
7 4
17 30
2 18
38 8
21 24
1 13
4 28
18 24
17 21
25 14
7 3
48 2
36 9
50 22 8 8 756 883 690
16 11
8 30
45 3
42 6
26 22
7 39
4 27
19 7
14 20
48 2
15 8
9 1
3 15
16 4
1 6
39 10
15 28
27 2
34 11
26 14
33 14
2 7
15 27
5 27
19 8
17 5
11 24
2 44
9 41
7 39
8 14
3 3
34 11
16 32
35 14
12 13
12 19
7 20
36 12
15 27
3 22
1 22
19 4
5 14
37 8
43 1
9 31
2 21
12 29
16 7
50 21 18 2 471 299 613
8 10
19 20
20 11
39 11
46 4
30 17
13 27
19 6
16 24
29 1
25 14
37 8
25 3
22 27
18 22
15 10
10 7
25 12
36 11
14 4
27 22
7 27
33 3
8 24
5 27
24 14
33 4
7 41
16 26
37 9
26 8
18 15
14 36
21 4
34 4
5 44
19 20
18 23
10 40
12 14
10 15
42 3
25 21
31 11
18 14
12 9
2 3
17 10
10 1
26 4
50 9 2 19 627 406 191
7 33
14 32
13 19
2 28
2 8
16 34
6 12
5 16
6 4
43 7
2 35
6 16
28 10
40 7
39 6
1 43
27 7
18 23
12 33
23 4
16 30
29 11
7 35
18 1
14 5
42 2
18 25
13 27
31 11
19 1
2 2
31 14
1 36
23 15
9 34
10 35
48 2
7 18
12 27
22 22
20 15
7 2
13 1
10 3
4 45
15 24
1 36
17 5
14 23
39 5
50 2 6 6 223 60 491
39 3
27 12
21 2
39 5
2 1
12 2
35 9
15 12
6 33
6 18
2 16
9 40
15 15
6 23
8 1
16 6
29 18
14 12
10 11
2 41
3 13
6 11
12 11
15 6
22 21
44 5
14 17
14 15
1 11
6 25
6 43
17 7
12 27
5 40
18 19
15 30
22 5
4 34
1 14
19 30
23 5
4 31
28 13
28 4
5 30
6 23
27 20
5 10
2 33
10 29
Little Elephants
The Little Elephant and his friends from the Zoo were returning from the party. But suddenly they were stopped by the policeman Big Hippo, who wanted to make an alcohol test for elephants.
There were N elephants ordered from the left to the right in a row and numbered from 0 to N-1.Let R[i] to be the result of breathalyzer test of i-th elephant.
Considering current laws in the Zoo, elephants would be arrested if there exist K consecutive elephants among them for which at least M of these K elephants have the maximal test result among these K elephants.
Using poor math notations we can alternatively define this as follows. The elephants would be arrested if there exists i from 0 to N-K, inclusive, such that for at least M different values of j from i to i+K-1,inclusive, we have R[j] = max{R[i], R[i+1], ..., R[i+K-1]}.
The Big Hippo is very old and the Little Elephant can change some of the results. In a single operation he can add 1 to the result of any elephant. But for each of the elephants he can apply this operation at most once.
What is the minimum number of operations that the Little Elephant needs to apply, such that the sequence of results, after all operations will be applied, let elephants to avoid the arrest? If it is impossible to avoid the arrest applying any number of operations, output -1.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three space-separated integers N,K, M. The second line contains N space-separated integers R[0],R[1], ..., R[N-1] denoting the test results of the elephants.
Output
For each test case, output a single line containing the minimum number of operations needed to avoid the arrest.
Constraints
1 ≤ T ≤ 10
1 ≤ M ≤ K ≤ N ≤ 17
1 ≤ R[i] ≤ 17
Example
Input:
4
5 3 2
1 3 1 2 1
5 3 3
7 7 7 7 7
5 3 3
7 7 7 8 8
4 3 1
1 3 1 2
Output:
#1 0
#2 1
#3 1
#4 -1
Explanation
Example case 1. Let's follow the poor math definition of arrest. We will consider all values of i from 0 to N-K = 2, inclusive, and should count the number of values of j described in the definition. If it less than M = 2 then this value of i does not cause the arrest, otherwise causes.
i
{R[i],...,R[i+K-1]}
max{R[i],...,R[i+K-1]}
For which j = i, ..., i+K-1
we have R[j] = max
Conclusion
i=0
{1, 3, 1}
max = 3
R[j] = 3 for j = 1
does not cause the arrest
i=1
{3, 1, 2}
max = 3
R[j] = 3 for j = 1
does not cause the arrest
i=2
{1, 2, 1}
max = 2
R[j] = 2 for j = 3
does not cause the arrest
So we see that initial test results of the elephants do not cause their arrest. Hence the Little Elephant does not need to apply any operations. Therefore, the answer is 0.
Example case 2.Wehave N = 5, K = 3, M = 3. Let's construct similar table as in example case 1. Here the value of i will cause the arrest if we have at least 3 values of j described in the definition.
i
{R[i],...,R[i+K-1]}
max{R[i],...,R[i+K-1]}
For which j = i, ..., i+K-1
we have R[j] = max
Conclusion
i=0
{7, 7, 7}
max = 7
R[j] = 7 for j = 0, 1, 2
causes the arrest
i=1
{7, 7, 7}
max = 7
R[j] = 7 for j = 1, 2, 3
causes the arrest
i=2
{7, 7, 7}
max = 7
R[j] = 7 for j = 2, 3, 4
causes the arrest
So we see that for initial test results of the elephants each value of i causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding1 to the result R[2]. Then results will be {R[0], R[1], R[2], R[3],R[4]} = {7, 7, 8, 7, 7}. Let's check that now elephants will be not arrested.
i
{R[i],...,R[i+K-1]}
max{R[i],...,R[i+K-1]}
For which j = i, ..., i+K-1
we have R[j] = max
Conclusion
i=0
{7, 7, 8}
max = 8
R[j] = 8 for j = 2
does not cause the arrest
i=1
{7, 8, 7}
max = 8
R[j] = 8 for j = 2
does not cause the arrest
i=2
{8, 7, 7}
max = 8
R[j] = 8 for j = 2
does not cause the arrest
So we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can't avoid the arrest but using 1 operation can. Hence the answer is 1.
Example case 3.Wehave N = 5, K = 3, M = 3. Let's construct similar table as in example case 1. Here the value of i will cause the arrest if we have at least 3 values of j described in the definition.
i
{R[i],...,R[i+K-1]}
max{R[i],...,R[i+K-1]}
For which j = i, ..., i+K-1
we have R[j] = max
Conclusion
i=0
{7, 7, 7}
max = 7
R[j] = 7 for j = 0, 1, 2
causes the arrest
i=1
{7, 7, 8}
max = 8
R[j] = 8 for j = 3
does not cause the arrest
i=2
{7, 8, 8}
max = 8
R[j] = 8 for j = 3, 4
does not cause the arrest
So we see that for initial test results of the elephants the value of i =0 causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding1 to the result R[1]. Then results will be {R[0], R[1], R[2],R[3], R[4]} = {7, 8, 7, 8, 8}. Let's check that now elephants will be not arrested.
i
{R[i],...,R[i+K-1]}
max{R[i],...,R[i+K-1]}
For which j = i, ..., i+K-1
we have R[j] = max
Conclusion
i=0
{7, 8, 7}
max = 8
R[j] = 8 for j = 1
does not cause the arrest
i=1
{8, 7, 8}
max = 8
R[j] = 8 for j = 1, 3
does not cause the arrest
i=2
{7, 8, 8}
max = 8
R[j] = 8 for j = 3, 4
does not cause the arrest
So we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can't avoid the arrest but using 1 operation can. Hence the answer is 1. Note that if we increase by 1 the result R[2] instead of R[1] then the value i = 2 will cause the arrest since {R[2], R[3], R[4]}will be {8, 8, 8} after this operation and we will have 3 values of j from 2 to 4,inclusive, for which R[j] = max{R[2], R[3], R[4]}, namely, j= 2, 3, 4.
Example case 4. When M= 1 the Little Elephant can't reach the goal since for each value of i from 0 to N-K we have at least one value of j for which R[j] =max{R[i], R[i+1], ..., R[i+K-1]}.
//test case
50
5 3 2
1 3 1 2 1
5 3 3
7 7 7 7 7
5 3 3
7 7 7 8 8
4 3 1
1 3 1 2
9 3 2
16 4 6 1 9 9 5 2 1
7 4 4
2 10 10 10 10 10 3
9 3 3
5 1 1 7 1 1 1 1 1
7 2 2
10 2 9 17 12 11 4
17 14 14
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 13
2 2 2
5 5
14 9 6
7 6 11 14 6 7 7 7 7 7 7 7 7 7
4 2 1
3 8 15 9
6 3 3
15 15 15 15 3 7
1 1 1
1
5 2 2
14 14 14 7 5
8 2 2
4 16 4 4 4 4 4 4
6 2 2
2 15 17 17 17 17
8 3 2
5 8 17 16 16 16 7 7
15 9 9
10 10 10 10 10 10 10 10 10 10 10 10 10 16 3
7 6 5
9 3 14 12 12 12 10
3 3 3
6 3 17
11 11 2
4 5 4 10 16 12 10 3 3 10 10
2 2 2
3 3
4 2 2
1 16 8 8
5 4 2
17 3 8 13 13
17 7 6
3 3 3 3 3 3 3 3 3 3 3 15 11 6 8 10 6
17 5 5
17 5 5 5 5 5 5 5 5 5 5 12 12 12 12 12 15
8 3 2
11 7 6 6 6 13 14 8
1 1 1
2
2 2 1
12 9
7 6 3
1 1 1 7 14 7 13
9 8 7
12 14 16 5 7 1 6 3 17
5 2 2
2 6 6 6 6
15 5 5
16 3 6 17 17 17 17 17 17 17 17 17 17 17 17
17 5 5
17 9 8 4 2 7 7 16 10 7 14 12 6 5 3 6 1
3 2 2
10 10 10
17 5 5
4 4 4 4 4 4 4 4 12 6 2 9 8 13 10 9 2
14 6 5
2 5 9 13 4 8 12 16 4 14 17 6 5 9
6 6 2
6 2 16 16 16 16
5 3 2
10 11 9 2 4
15 5 4
7 7 7 7 7 7 7 7 7 2 6 5 14 1 14
14 4 3
15 3 3 3 3 3 3 3 3 3 5 3 14 3
9 4 3
13 13 13 13 13 13 11 4 16
7 3 3
1 7 2 2 2 8 3
5 4 3
13 8 1 13 1
11 4 2
13 13 12 14 2 9 8 10 7 3 9
10 8 8
7 7 7 7 7 7 7 7 7 7
5 3 1
7 6 4 16 16
10 5 5
3 6 6 6 6 6 6 6 1 14
4 2 2
12 12 12 16
Editor is loading...