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!
888 - Donkey
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Re: 888 - Donkey
The other two people are not the worlds worst problemsolvers, and not many people have tried this problem yet, which makes me doubt the correctness of your program.Christian Schuster wrote: 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!
If you want, you can PM me your code and I'll run it against the judges input to resolve both our doubts.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 888 - Donkey
Input:
AC output:
Code: Select all
7
3 2 1 2 1
6 3 1 2 3 2
6 3 4 1 3 2
42 1 15 1
22 2 10 12 2
13 3 8 2 9 2
8 4 7 4 1 6 3
Code: Select all
Game 1:the probability that player 1 wins = 0.667
Game 2:the probability that player 1 wins = 0.093
Game 3:the probability that player 1 wins = 0.366
Game 4:the probability that player 1 wins = 1.000
Game 5:the probability that player 1 wins = 0.224
Game 6:the probability that player 1 wins = 0.212
Game 7:the probability that player 1 wins = 0.222
Check input and AC output for thousands of problems on uDebug!
-
- Experienced poster
- Posts: 139
- Joined: Wed May 18, 2011 3:04 pm
Re: 888 - Donkey
This problem should employ special judge.
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.