SHARE
TWEET

rozwiązanie autora - n=5: 63.806125%

a guest Jul 11th, 2016 10 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <math.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define TEST_N 5
  6. #define START_AT 0.0
  7. #define RUNS 100000000
  8.  
  9. #define PREC 10000
  10. #define SZ 1009
  11. #define false 0
  12. #define true 1
  13. #define bool int
  14.  
  15.   static double prev_max = 0;
  16. double M;
  17. double cache[PREC+1][SZ];
  18. void reset(double r){
  19. prev_max=0;
  20. }
  21.  
  22. double R(double m, int n){
  23.     int mint=(int)(m*PREC);
  24.     if(n==1){
  25.         return 1-m;
  26.     }
  27.     else if(cache[mint][n]>=0){
  28.         return cache[mint][n];
  29.     }
  30.     else{
  31.         double sum=0;
  32.         int cnt=0;
  33.         for(int i=0;i<=PREC;i++){
  34.             double v=(i+0.00001)/PREC;
  35.             if( v<m ){ cnt++; }
  36.             else{
  37.                 if(pow(v, n-1)>R(v, n-1)){
  38.                     sum+=pow(v,n-1);
  39.                 }
  40.                 else{
  41.                     sum+=R(v, n-1);
  42.                 }
  43.             }
  44.         }
  45.         sum+=cnt*R(m, n-1);
  46.         return cache[mint][n]=sum/(PREC+1);
  47.     }
  48. }
  49.  
  50. int guess_max(double x, int N, int count) {
  51.   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ć */
  52.      return 0;
  53.   prev_max = x;
  54.  
  55.   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 */
  56. }
  57.  
  58. void print(int n){
  59.     for(int nn=1;nn<=n;nn++){
  60.         printf("For N=%d: total - %lf%%, other:\nM%% ", nn, R(START_AT, nn)*100);
  61.         for(int i=0;i<100;i+=2){
  62.             printf("%2d ",i);
  63.         }
  64.         printf("\nR%% ");
  65.         for(int i=0;i<100;i+=2){
  66.             printf("%2d ",(int)(99.9999*R(i/100.0, nn)));
  67.         }
  68.         printf("\n");
  69.     }
  70.     printf("R(START, N)=%lf%%\n", 100*R(START_AT, n));
  71. }
  72.  
  73. int main(){
  74.     //reset(START_AT);
  75.     int cnt=0;
  76.     int N=TEST_N;
  77.     //print(N);
  78.     int runs=RUNS;
  79.     for(int i=0;i<runs;i++){
  80.         reset(START_AT);
  81.         srand(i);
  82.         double real_max = START_AT;
  83.         double your_max = -1;
  84.         int done = 0;
  85.      
  86.         for(int count=1; count<=N; count++) {
  87.             double x=rand()/(double)RAND_MAX;
  88.             if (!done && (done = guess_max(x, N, count))) {
  89.                 your_max = x;
  90.             }
  91.             if (real_max < x) {
  92.                 real_max = x;
  93.             }
  94.         }
  95.         if(your_max >= real_max-1e-12) {
  96.             cnt++;
  97.         }
  98.     }
  99.     printf("Empirical accuracy for N=%d: %lf%%\n", N, cnt/(double)runs*100);
  100. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top