[题解]the moon

题面

The Moon

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1120 Accepted Submission(s): 497
Special Judge

Problem Description

The Moon card shows a large, full moon in the night’s sky, positioned between two large towers. The Moon is a symbol of intuition, dreams, and the unconscious. The light of the moon is dim, compared to the sun, and only vaguely illuminates the path to higher consciousness which winds between the two towers.

Random Six is a FPS game made by VBI(Various Bug Institution). There is a gift named “Beta Pack”. Mr. K wants to get a beta pack. Here is the rule.
Step 0. Let initial chance rate q = 2%.
Step 1. Player plays a round of the game with winning rate p.
Step 2. If the player wins, then will go to Step 3 else go to Step 4.
Step 3. Player gets a beta pack with probability q. If he doesn’t get it, let q = min(100%, q + 2%) and he will go to Step 1.
Step 4. Let q = min(100%, q + 1.5%) and goto Step 1.
Mr. K has winning rate p% , he wants to know what’s the expected number of rounds before he needs to play.

Input

The first line contains testcase number T (T ≤ 100). For each testcase the first line contains an integer p (1 ≤ p ≤ 100).

Output

For each testcase print Case i : and then print the answer in one line, with absolute or relative error not exceeding 106.

Sample Input

2
50
100

Sample Output

Case 1: 12.9933758002
Case 2: 8.5431270393

Source

2018CCPC吉林赛区（重现赛）

---

题解

题目大意:

• 给你一个胜率p，和一个初始中奖率q=2%，每次玩一局游戏。

• 如果游戏赢了就抽奖：
  - 没抽到就q+2%，然后继续玩游戏。
  - 抽到了就直接结束游戏。

• 如果游戏输了就q+1.5%，然后继续玩游戏。

  问玩的游戏局数的期望，并且中奖率最高为100%

思路：

1. 首先题目求期望，推测是概率dp逆推。

2. 确定dp定义，求什么就用什么，定义dp[i]为当得到概率q为i时游戏局数的期望。 因为i的范围是[0, 1]，所以为了方便dp，让$i=q\ast 1000$；

3. 所以我们应该从dp[1000]逆推到dp[20]，dp[20]就是答案

4. dp[1000]就相当于求对于一个胜率为Q的游戏的胜利局数期望
   $Ex=Q+(1-Q)Q+(1-Q{)}^{2}Q+..$
   可以看出上面的式子是等差数列，求和得1/Q。所以dp[1000]=1/q;

5. 再考虑递推式：

   • $dp[i]+=p\ast (1-q)\ast (1+dp[min(i+20,1000)];$ 赢了但是没有得到

   • $dp[i]+=(1-p)\ast (1+dp[min(i+15,1000)];$ 输了

   • $dp[i]+=p\ast q$; 赢了且得到

   • 所以 $dp[i]=p\ast (1-q)\ast (1+dp[min(i+20,1000)]+(1-p)\ast (1+dp[min(i+15,1000)]+p\ast q$

   注意：上面dp要+1的原因是因为本局也要加上去。

6. 用个for递推dp即可，直接打码。

代码 ：

#define Oo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
double dp[1005];
int main()
{
      Oo
      int t;
      cin>>t;
      for(int flag=1; flag<=t; flag++)
      {
            double p;cin>>p;
            p=p/100.0;
            dp[1000]=1.0/p;
            for (int i=999; i>=20; i--)
            {
                  double q=i/1000.0;
                  dp[i]=p*(1-q)*(1+dp[min(1000,i+20)])+(1-p)*(1+dp[min(i+15,1000)])+p*q;
            }
            cout << "Case "<<flag<<": " ;
            cout <<fixed<< setprecision(10) << dp[20] << endl;
      }
	return 0;
}

个人hexo博客.