Блог пользователя dbedi3311

Автор dbedi3311, история, 3 года назад, По-английски

I came across this problem in UVa OJ called 1413-Game (UVa-1413 Game). The problem statement is essentially as follows: A group of contestants sits at a round table and they pass around a token to an adjacent person (either to their left or right) with a certain probability. The person who receives the token does the same with his/her probability and so on. The game stops once each person has received the token at least once, and the last person with the token wins.

Given input the number of contestants, n (0 <= n <= 50), and the number of the contestant who starts with the token, k (k < n) as well as a list of probabilities p_i that contest i passes the token to the right, determine the probability that contestant n wins the game. Your output should be accurate to 6 digits after the decimal.

I want to improve my probability implementation skills, especially since I think it will be relevant for ICPC. Let me know of any solutions (preferably with code-attached) I can view.

As a side note: this problem was taken from Art of Algorithms for Programming Contests Training Guide by Ruijia Liu. If anyone has access to a pdf, preferably in English, of the book and wouldn't mind sending it over, that would be much appreciated.

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Let $$$probLeft[l,r,flag]$$$ be the probability that if the token has covered the range $$$[l,r]$$$ and it's currently at position $$$flag$$$ ( either $$$l$$$ or $$$r$$$) the token will next visit $$$l-1$$$ before visiting $$$r+1$$$.

If you precalculate this probabilities then you can calculate the answer with another $$$dp[l,r,flag]$$$