題面

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 ? 1000 i=q*1000 i=q?1000；

3. 所以我們應該從dp[1000]逆推到dp[20]，dp[20]就是答案

4. dp[1000]就相當于求對于一個勝率為Q的游戲的勝利局數期望
   E x = Q + ( 1 ? Q ) Q + ( 1 ? Q ) 2 Q + . . Ex=Q+(1?Q)Q+(1?Q)^2Q+.. Ex=Q+(1?Q)Q+(1?Q)2Q+..
   可以看出上面的式子是等引數列，求和得1/Q，所以dp[1000]=1/q;

5. 再考慮遞推式：

   • d p [ i ] + = p ? ( 1 ? q ) ? ( 1 + d p [ m i n ( i + 20 , 1000 ) ] ; dp[i]+=p*(1-q)*(1+dp[min(i+20, 1000)]; dp[i]+=p?(1?q)?(1+dp[min(i+20,1000)]; 贏了但是沒有得到

   • d p [ i ] + = ( 1 ? p ) ? ( 1 + d p [ m i n ( i + 15 , 1000 ) ] ; dp[i]+=(1-p)*(1+dp[min(i+15, 1000)]; dp[i]+=(1?p)?(1+dp[min(i+15,1000)]; 輸了

   • d p [ i ] + = p ? q dp[i]+=p*q dp[i]+=p?q; 贏了且得到

   • 所以 d p [ i ] = p ? ( 1 ? q ) ? ( 1 + d p [ m i n ( i + 20 , 1000 ) ] + ( 1 ? p ) ? ( 1 + d p [ m i n ( i + 15 , 1000 ) ] + p ? q dp[i]=p*(1-q)*(1+dp[min(i+20, 1000)]+(1-p)*(1+dp[min(i+15, 1000)]+p*q dp[i]=p?(1?q)?(1+dp[min(i+20,1000)]+(1?p)?(1+dp[min(i+15,1000)]+p?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博客.