This task is based upon the small game which I found in the great book of French author Jacques Arsac:
Jeux et casse-tête à programmer (Programming of games and puzzles) - Dunod, 1985
I'm afraid it is not translated into English, so here is the description of the game:
There is a road consisting of several lines - see the demo above. The cars depicted as $ are travelling from
right to left. The cars at topmost line have speed of 5 - i.e. they move 5 positions left on each turn. The cars
at the second line have the speed of 6, at the third - 7 and so on. Symbols + mark the future position of each
car for convenience (though at the current move these places are as empty as others, marked with -).
The distance between cars in the first line is 18 (i.e. there are 17 empty spaces between them), in the second -
19 and so on, also increasing by 1 with each line.
There is a guy trying to cross the road. He starts from the leftmost position of the first line. We use mark @ for
him. At each move he can do one of three things: either step back to previous line (except when he is at the topmost
of them), step forth to the next line, or stay where he is.
You can control guy with keys z to move forward, q to step back and a to stay for one turn.
After guy's move cars' positions are adjusted too. If at this point it appears that some car run over this unhappy person, he is smashed and dead. The game is over.
This condition is determined as follows - if before its move the car (on the same line with the guy) was at position
x>=0 and after the move its position is x<=0 then the deadly accident have occured (suggesting that 0 is the
coordinate of leftmost ends of lines, where guy crosses the road).
Player wins if the guy advances forth from the last line (i.e. to the sidewalk of the opposite side).
Play the demo a bit to understand the rules better - or consider the following example:
Initial position After the first move
@----------+----$------------+----$----- ------+----$------------+----$----------
--+-----$------------+-----$------------ @-$------------+-----$------------------
------+------$------------+------$------ ------$------------+------$-------------
-+-------$------------+-------$--------- -$------------+-------$-----------------
-----+--------$------------+--------$--- -----$------------+--------$------------
--+---------$------------+---------$---- --$------------+---------$--------------
-----+----------$----------------------- -----$------------+----------$----------
-+-----------$------------+-----------$- -$------------+-----------$-------------
You will be given description of the initial position of the cars (only first car in each line since others follow at the known distance) - and you need to find out the minimum number of turns in which the game could be won.
For example, the game with initial position shown above could be solved in 19 turns (i.e. the 19-th step will
bring the guy from the last line to safety on a sidewalk).
Note that in contrast with demo above, you will face a road with 11 lines to avoid giving you too easy task!
Input data will contain the number of games in the first line.
Then each line will give 11 values - starting positions of the closest car in each line.
Answer should give the minimum number of steps after which each game could be won or -1 if there is no
winning sequence of moves.
Example:
input data:
3
13 18 18 5 1 10 4 13 21 1 19
12 11 7 14 6 6 18 17 8 7 18
17 6 11 17 12 11 7 9 20 5 11
answer:
50 35 -1