Codeforces Round #499 (Div. 2) C.FLY 数学推导

本题应该是可以使用实数二分的，不过笔者一直未调出来，而且发现了一种更为优美的解法，那就是逆推。

首先，不难猜到在最优解中当飞船回到 111 号节点时油量一定为 000，这就意味着减少的油量等于减少之前的油量，即 fuel=mb1−1fuel=\frac{m}{b_{1}-1}fuel=b1−1m

我们还可以将起飞和降落视为同一种操作，将公式进行变换，就得到 :

fuel′=ai∗fuel+mai−1fuel'=\frac{a_{i}*fuel+m}{a_{i}-1}fuel′=ai−1ai∗fuel+m 和 fuel′=bi∗fuel+mbi−1fuel'=\frac{b_{i}*fuel+m}{b_{i}-1}fuel′=bi−1bi∗fuel+m，特判一下 iii 是否等于 111 即可。

Code:

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn = 1000 + 4;

int a[maxn], b[maxn];

int main()

{

    int n, m;

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n; ++i)

    {

        scanf("%d",&a[i]);

        if(a[i] <= 1) { printf("-1"); return 0; }

    }

    for(int i = 1;i <= n; ++i)

    {

        scanf("%d",&b[i]);

        if(b[i] <= 1) { printf("-1"); return 0; }

    }

    double ans = (double) m / (b[1] - 1);

    for(int i = n; i >= 1;--i)

    {

        ans = (double)(a[i] * ans + m) / (a[i] - 1);

        if(i != 1) ans = (b[i] * ans + m) /(b[i] - 1);

    }

    printf("%.10lf",ans);

    return 0;

}

巴特西

Codeforces Round #499 (Div. 2) C.FLY 数学推导_逆推

最新文章

热门文章