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

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 172 |

2 | awoo | 167 |

3 | SecondThread | 163 |

4 | BledDest | 162 |

4 | Um_nik | 162 |

6 | maroonrk | 161 |

6 | nor | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

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

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/01/2023 16:34:30 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

As far as I remember, when

nis 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 andk= 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...