题解 AT2170 【Pushing Balls】

litble · 2018-10-19 16:35:53 · 题解

戳我＝￣ω￣＝

我们来到操场的沙坑上，赶走在练习跳远的人，然后挖四个坑，然后找体育组借三个实心球放在四个坑直接，那么这些物品两两的初始距离是：

考虑一下不同的推球方法，当一个球进入一个坑后，就默不作声地用沙子将这个球埋起来，假装什么都没有发生过，将这些球重新编号。你会发现物品两两间距离有这么几种可能（表格头的编号是重编过的）：

哇，好神奇啊，期望的物品间距离居然还是个等差数列～

你会对这个发现感到异常惊奇，但还是不要忘了把实心球挖出来还回去。

现在来观察，等差数列的第一项就是我们表格的坑1与球1这一列，你会发现不管初始用几个球，这一列只有前两行是d+2x和3d+3x，其他行都是d。所以d'=d+\frac{2d+5x}{2n}。至于公差，我们观察一下球2与坑2这一列，发现这一列的期望永远会是d+x+\frac{2d+9x}{2n}，所以公差x'=x+\frac{4x}{2n}。

这样我们做n次对d和x（其实还有n别忘了）的变换，即可得到答案。

oh，对，至于每种局面下的推球期望距离，应该是d+\frac{2n-1}{2x}，具体为什么自己推(zhǎo)一(guī)推(lǜ)吧。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
int n;db d,x,ans;
int main()
{
    scanf("%d%lf%lf",&n,&d,&x);
    db nn=n+n;
    for(RI i=n;i>=1;--i) {
        ans+=d+(nn-1)/2*x;
        db dd=d+(2*d+5*x)/nn;
        db xx=x+4*x/nn;
        x=xx,d=dd,nn-=2;
    }
    printf("%.10lf\n",ans);
    return 0;
}