_QWOiNYUIVMPFSBKLiGSMAP_'s blog

By _QWOiNYUIVMPFSBKLiGSMAP_, history, 7 years ago, In English

why in the second testcase the answer is not ...XXX http://codeforces.net/contest/104/problem/D

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As far as I remember, when n is an even number, all the positions can be divided into two types: odd positions and even positions. The reason is that two players move in turn, and for any single player, if he starts at an even/odd position, he will always "stay" at even/odd positions.

Thus, for n = 6 and k = 3 bullets, if we put all the three bullets at even positions or odd positions, the winning probability is 0.5, since this result in fact only depends on whether the starting position is even or odd. However, if we do not follow the above rules, the winning probability will be decreased. For instance, if it is "...XXX", you can see that we only win if the starting position is 1 and 3, which gives a winning probability 2/6<0.5. Nevertheless, the general case seems difficult to prove...