Hello folks. This problem seemd quite simple to me: Some backtracking+memoization (or DP) should be sufficient. However, I got a bunch of WAs within times comparable to the AC solutions. My solution uses the tuple of distances to the capital as memoization key. As I don't think my calculations are prone to floating point errors, there must be something else.
Are there any tricky cases? The only "special" case I could imagine is M=0, for which the result is 1.000 if player 1 starts, or 0.000 otherwise.
Except the creators of the input file, only two people got it AC yet, which makes me doubt the correctness of the input file. Please resolve my doubts!
![;)](./images/smilies/icon_wink.gif)