小Q与氪金游戏

游戏"/>

小Q与氪金游戏

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
Special Judge, 64bit IO Format: %lld

题目描述 

“为世界上所有的美好而战！”
小Q同学最近沉迷“稳固3”，为了从最新的蛋池中抽出自己喜欢的角色卡，不惜氪下重金。
在这个游戏中，氪一单可以得到x个宝石，而抽一次卡需要花费y个宝石，由于游戏策划十分“良心”，抽卡是独立重复实验，单次抽出目标角色卡的概率是p且不存在所谓的“保底”。
为了尽可能省钱，小Q同学只会在抽卡所需宝石不足的情况下再氪一单，并且抽出目标角色卡之后会立即停止抽卡，他想知道为了抽出目标角色卡期望要氪多少单。

输入描述:

输入只有一行，包含三个整数x,y,q(0<x,y,q<10000)，分别表示氪一单能得到的宝石数、抽一次卡需要的宝石数以及抽出目标角色卡的概率p乘以10000之后的数。

输出描述:

输出一行，包含一个浮点数，表示抽出目标角色卡期望氪的单数，要求绝对误差或相对误差不超过 1e-9。

示例1

输入

6480 280 98

输出

4.921219218795631382

解题思路：模拟一下整个过程，多模拟几次

#include <iostream>    
#include <cstdio>    
#include <cstring>    
#include <string>    
#include <algorithm>    
#include <map>    
#include <set>    
#include <stack>    
#include <queue>    
#include <vector>    
#include <bitset>    
#include <functional>    using namespace std;#define LL long long    
const int INF = 0x3f3f3f3f;int x, y, q;
double a[100009], b[100009];int main()
{while (~scanf("%d%d%d", &x, &y, &q)){double p = 1.0 * q / 10000.0;a[0] = b[0] = 1.0;for (int i = 1; i <= 20000; i++){a[i] = a[i - 1] * (1.0 - p);b[i] = b[i - 1] + a[i];}double pp = 1.0, ans = 0.0;int sum = 0;LL cnt = 0;for (int i = 1; i <= 1000000; i++){int tmp = y - sum;int ke = tmp / x;if (tmp % x) ke++;cnt = cnt + 1LL * ke;sum = sum + ke * x;int res = sum / y;ans = ans + 1.0 * pp * p * cnt * b[res - 1];sum = sum % y;pp = pp * a[res];}printf("%.20f\n", ans);}return 0;
}