F-Fireworks（概率，三分）

题目描述

Kotori is practicing making fireworks for the upcoming hanabi taikai ^1^ . It takes her n minutes to make a single firework, and as she is not really proficient in making fireworks, each firework only has a probability of $p×10^{-4}$ to be perfect.

After she finishes making a firework, she can just start making the next firework, or take m minutes to light all the remaining fireworks finished before. If there is at least one perfect firework among the lit ones, she will be happy and go to rest. Otherwise, she will continue practicing. Can you tell her the minimum expected practicing time before she goes to rest if she takes the optimal strategy?

Notice that no matter how many fireworks remain, it always takes m minutes to light them all.

^1^Hanabi taikai: Romaji of the Japanese word "花火大會", which means the firework... err... party?

alt

输入样例

输出样例

4.0000000000
10141.5852891136
3.0000000000

题意简介

一个名叫Kotori的人在练习造烟花。

他有两种操作：

继续造一个烟花，花费n时间
把之前造好的还没有放的烟花燃放，不管多少烟花，燃放时间都是m，并且在燃放过程中可以检验烟花是不是perfect

当燃放的烟花中有一个正常，那么就跑去休息。

问：如果要是休息，那么最小的期望是多少？

题解

在一开始，我们并没有看懂样例。。。

由于Kotori并不知道他造好的烟花究竟是不是perfect，所以按照一般的理解。

如果造烟花完美的概率是1，那么肯定造一个，放一个。

如果造烟花完美的概率非常低，那么我就没有必要造一个，放一个。多造几个，然后再进行燃放显然是更加优秀。

所以：我们仅仅需要求出，在连续造k个烟花，然后燃放这样的情况下所需要的时间里面的最短的哪一个就可以了。

如果要是造了K个，燃放，失败了，那么他下一次仍然是要造了K个，燃放，不会改变k的值，因为要确保一直是最优的情况。

对此，有一个公式(设p表示造烟花造失败的概率)

E_x = (k\times n+m)\times(1-p^k) + (k\times n+m+E_x)\times p^k

把这一个方程进行化简，那么就会有

E_x = \frac{a\times k+b}{1-p^k}

代码

#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
int n, m, p;
double q;

double cal(int x)
{
    return ((double)n*x+m)/((double)1-pow(q, x));
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &p);
        q = 1 -  1.0*p/10000;
        int L = 1, R = 0x3f3f3f3f;
        while(L+10 < R)
        {
            int lmid = L+(R-L)/3;
            int rmid = R-(R-L)/3;
            if(cal(lmid) > cal(rmid))
            {
                L = lmid;
            }
            else {
                R = rmid;
            }
        }
        double ans = cal(L);
        for(int i = L+1; i <= R; i++)
        {
            ans = min(ans, cal(i));
        }
        printf("%.10lf\n", ans);
        //cout << n<<" "<<m<<" "<<p;
    }
    return 0;
}

题解 | #Fireworks#

F-Fireworks（概率，三分）

题目描述

题意简介

题解

代码