1622 - Robot

[brianfry713]

Input:

Code: Select all

4 7
8 6 4 6
7 3
10 2 3 8
1 10
4 7 1 7
3 7
2 9 8 10
3 1
3 4 8 6
10 3
3 9 10 8
4 7
2 3 10 4
2 10
5 8 9 5
6 1
4 7 2 1
7 4
3 1 7 2
6 6
5 8 7 6
7 10
4 8 5 6
3 6
5 8 5 5
4 1
8 9 7 9
9 5
4 2 5 10
3 1
7 9 10 3
7 7
5 10 6 1
5 9
8 2 8 3
8 3
3 7 2 1
7 2
6 10 5 10
0 0

AC output:

Code: Select all

Case 1: 493
Case 2: 226
Case 3: 67
Case 4: 402
Case 5: 17
Case 6: 585
Case 7: 376
Case 8: 338
Case 9: 58
Case 10: 220
Case 11: 721
Case 12: 1330
Case 13: 283
Case 14: 55
Case 15: 671
Case 16: 34
Case 17: 737
Case 18: 597
Case 19: 235
Case 20: 248

[12061160]

still WA...could you give me some logic thoughts?

[brianfry713]

In this and many problems I solved it by writing a random test case generator for small input values (<= 10), then a brute force solution using backtracking that would TLE for large input values, and then work on getting correct code that will run in the time limit.
To simplify I swapped equivalent values to make NORTH >= SOUTH, and WEST >= EAST.
Then there are two main cases to handle: the first move north or the first move west. You should try both and see which gives a larger answer.
If your first move is north then you keep moving south then north until you run out of south moves. After that make a move west then keep moving east then west until you run out of east moves.
Now your only remaining moves are north and west. If the height of the remaining grid of robots is >= width then move north, otherwise move west. Continue until your run out of robots or run out of moves.

[12061160]

Already AC!Thanks for random test cases~~

In this and many problems I solved it by writing a random test case generator for small input values (<= 10), then a brute force solution using backtracking that would TLE for large input values, and then work on getting correct code that will run in the time limit.
To simplify I swapped equivalent values to make NORTH >= SOUTH, and WEST >= EAST.
Then there are two main cases to handle: the first move north or the first move west. You should try both and see which gives a larger answer.
If your first move is north then you keep moving south then north until you run out of south moves. After that make a move west then keep moving east then west until you run out of east moves.
Now your only remaining moves are north and west. If the height of the remaining grid of robots is >= width then move north, otherwise move west. Continue until your run out of robots or run out of moves.