I'll try to explain the last test case.

In this test case there are no possibility you will eventually knock down a domino to it's left side. So, it will be the best strategy to place the dominoes from left to right.

That is, if you place the dominoes from right to left, one eventual knockover will make all dominoes collapsed (so you will have to place all of them again). But when placing them from left to right one eventual knowover will cause only one domino to be placed again. (Of course in other cases it will be not this easy to determine the strategy)

So there are possibilities we have to place this single domino,

1.0 + 0.5 + (0.5 ^ 2) + (0.5 ^ 3) + ....

The first 1.0 means we have to place it AT LEAST ONCE.

So the summation of this infinite geometrical series is 2, and the expected cost for this single domino is 2. Therefore we have 2.0 * 10 = 20.00.

I think this explains all of your questions.

Anyway I've been wondering about this problem for a few days but could only figure out the outline....

Any helps would be appreciated!!

Thanks in advance,