Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. May be its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:
You have N domino tiles separated by different amounts (integer values that are given to you) and you know the height H of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile i is close enough (H or less) to tile i+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than H, what's the minimum amount of moves you need to make in order to have all the distances be at most H? You can't move the first nor the last tile. Print -1 if it is not possible.
Note: You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.
here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50) and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently http://www.spoj.pl/problems/TAP2012E/
d1 d2 d3 d4 ... d(n-1)
Minimum amount of moves.
2 4 4 1 4 3 2
1 2 2 2 2 2 2 2 3
2 2 2 2
1 6 2 4
-1 (NOT POSSIBLE)
I have only found a good solution for two cases:
D=sum_of_all_distances MaxPossible=(N-1)*H if D==MaxPossible and there is no di such that di>H Answer=0 else if D>MaxPossible Answer=-1