#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define TEST_N 1000
#define START_AT 0.0
#define RUNS 3000000

#define PREC 10000
#define SZ 1009
#define false 0
#define true 1
#define bool int

double M;
double cache[PREC+1][SZ];
void reset(double r){
    static bool done=false;
    if(!done){
        done=true;
        for(int i=0;i<=PREC;i++){
            for(int j=0;j<SZ;j++){
                cache[i][j]=-1;
            }
        }
    }
    M=r;
}

double R(double m, int n){
    int mint=(int)(m*PREC);
    if(n==1){
        return 1-m;
    }
    else if(cache[mint][n]>=0){
        return cache[mint][n];
    }
    else{
        double sum=0;
        int cnt=0;
        for(int i=0;i<=PREC;i++){
            double v=(i+0.00001)/PREC;
            if( v<m ){ cnt++; }
            else{
                if(pow(v, n-1)>R(v, n-1)){
                    sum+=pow(v,n-1);
                }
                else{
                    sum+=R(v, n-1);
                }
            }
        }
        sum+=cnt*R(m, n-1);
        return cache[mint][n]=sum/(PREC+1);
    }
}

int guess_max(double v, int ntotal, int count){
    int N=ntotal-count+1; // Numbers left.
    int res;
    if(v<M){
        res=0;
    }
    else if(N==1){
        res=1; // We fail anyway...
    }
    else{
        res = pow(v, N-1) > R(v, N-1);
    }
    if(v>M){ M=v; }
    return res;
}

void print(int n){
    for(int nn=1;nn<=n;nn++){
        printf("For N=%d: total - %lf%%, other:\nM%% ", nn, R(START_AT, nn)*100);
        for(int i=0;i<100;i+=2){
            printf("%2d ",i);
        }
        printf("\nR%% ");
        for(int i=0;i<100;i+=2){
            printf("%2d ",(int)(99.9999*R(i/100.0, nn)));
        }
        printf("\n");
    }
    printf("R(START, N)=%lf%%\n", 100*R(START_AT, n));
}

int main(){
    reset(START_AT);
    int cnt=0;
    int N=TEST_N;
    print(N);
    int runs=RUNS;
    for(int i=0;i<runs;i++){
        reset(START_AT);
        srand(i);
        double real_max = START_AT;
        double your_max = -1;
        int done = 0;

        for(int count=1; count<=N; count++) {
            double x=rand()/(double)RAND_MAX;
            if (!done && (done = guess_max(x, N, count))) {
                your_max = x;
            }
            if (real_max < x) {
                real_max = x;
            }
        }
        if(your_max >= real_max-1e-12) {
            cnt++;
        }
    }
    printf("Empirical accuracy for N=%d: %lf%%\n", N, cnt/(double)runs*100);
}