mayoko’s diary

プロコンとかいろいろ。

CODE FESTIVAL 2014 Hard A - eject

解法

単純に漸化式を解くだけです。

「n 回ボタンを押した時点で ON になっている確率」を  A_n とします。すると,
 A_{n+1} = p(1-A_n) + (1-p)A_n = (1-2p)A_n+p
特性方程式 x = (1-2p)x+p となるので,  x = \frac{1}{2}
よって,  A_n-\frac{1}{2} = -\frac{1}{2}(1-2p)^n(初期条件 A_0 = 0を考慮した)。
となるので, これをそのまま突っ込めば良いです。 double だと精度が悪いのか WA するので注意です。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long double p, n;
    cin >> p >> n;
    printf("%.10Lf\n", 0.5*(1-pow(1-2*p, n)));
    return 0;
}