题意：

你现在要打\(n\)个字符，但是程序随时可能会崩溃。

你可以在恰当的时机按下 \(Ctrl-S\)键，崩溃后，会从最后一次保存的情况继续开始打字。

具体是这样的：

• 在每个第\(i-0.1s(i>0)\)的时候，程序崩溃的概率为\(p\)
• 在每个第\(is(i \geq 0)\)的时候，你可以一口气按下\(x\)个键来存盘
• 在每个第\(i+0.1s(i \geq 0)\)的时候，你可以按下一个键来打字

求采取最优策略下，打完这\(n\)个字符，并且最后存盘，总按键次数的期望。

分析：

先不考虑可以存盘的情况，设\(d(i)\)为打印\(i\)个字符按键次数的期望。

有递推公式：\(d(i)=d(i-1)+1+p \cdot d(i)\)

当你打印出前\(i-1\)个字符，刚刚打完第\(i\)个的时候：

• 有概率\(p\)会崩掉，这时候要重新开始，还需要的按键数的期望为\(d(i)\)
• 有概率\(1-p\)没崩，打印完成了

化简一下得到：\(d(i)=\frac{1}{1-p}d(i-1)+\frac{1}{1-p}\)

然后再考虑存盘的情况，我们枚举存了\(x\)次盘，也就是把这\(n\)个字符分为\(x\)段，每打完一段就存一次盘。

由于\(\frac{1}{1-p}>1\)，可以看出\(d(n)\)是指数型增长的，所以就尽可能均匀地把\(n\)个字符分成\(x\)段。

或者也可以求一下\(d(n)\)的通项公式为：\(d(n)=\frac{1}{p(1-p)^n}-\frac{1}{p}\)来验证。

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 100000 + 10;const double INF = 1e20;double d[maxn];int main(){    int T; scanf("%d", &T);    for(int kase = 1; kase <= T; kase++) {        int n, x; double p;        scanf("%d%lf%d", &n, &p, &x);                d[0] = 0;        for(int i = 1; i <= n; i++) d[i] = (d[i - 1] + 1.0) / (1.0 - p);        double ans = INF;        for(int i = 1; i <= n; i++) {            int k = n / i, r = n % i;            ans = min(ans, r*d[k+1] + (i-r)*d[k] + i*x);        }        printf("Case #%d: %.6f\n", kase, ans);    }    return 0;}