rozwiązanie autora - n=5: 63.806125%

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

#define TEST_N 5
#define START_AT 0.0
#define RUNS 100000000

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

  static double prev_max = 0;
double M;
double cache[PREC+1][SZ];
void reset(double r){
prev_max=0;
}

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 x, int N, int count) {
  if ( x < prev_max ) /* Warto też pamiętać, jaka największa już była, bo jeśli teraz mamy mniejszą od niej, to nie ma co na nią stawiać */
     return 0;
  prev_max = x;

  return pow(x, N-count) > 0.5; /* Wystarczy sprawdzić, czy prawdopodobieństwo, że wśród pozostałych wszystkie będą mniejsze od x jest większe od zdarzenia przeciwnego */
}

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);
}