TOI 2015 Test 2 Problem C

toi2015-t2-pC.cpp

#include <cstdio>
#include <cmath>
using namespace std;

double p[100001];
double c[100000];

int main() {
    int maxn = 100000;
    p[1] = 1;
    c[0] = 1;
    for(int n = 2, l = 0, r = 1; n <= maxn; n++, r++) {
        // recompute c
        for(int i = r; i > l; i--)
            if((c[i] = (c[i] + c[i - 1]) / 2) < 1e-22) {
                if(i == r)
                    r--;
                else {
                    c[l = i] = 0;
                    break;
                }
            }
        c[0] /= 2;
        double pp = 0;
        for(int i = l + 1; i < r; i++)
            pp += c[i] * p[n - i];
        p[n] = (pp / 2 + pow(0.5, n - 1)) / (1 - pow(0.5, n));
        if(n == maxn)
            fprintf(stderr, "(%d, %d)\n", l, r);
    }
    // CBD (x45)  : 0.000014426949103667154302777821117675927098
    // no cut     : 0.000014426949103667208512886445392897627471 using 8.921 s (    0, 99999)
    // cut at 0   : 0.000014426949103667208512886445392897627471 using 3.640 s (43942, 56056)
    // cut 1e-100 : 0.000014426949103667208512886445392897627471 using 0.966 s (46676, 53327)
    // cut 1e-22  : 0.000014426949103667208512886445392897627471 using 0.443 s (48575, 51435)
    // cut 1e-10  : 0.000014426767339002582484137372775823138227 using 0.270 s (49214, 50806)
    printf("%.42f\n", p[maxn]);
}