#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NTRIALS 100000
#define MAXSIZE 100000
#define SIZE 100
int used[MAXSIZE]; //順列の配列

swapped(int n) //ランダムな順列を生成する
{
  int i, j, rnd;
  
  for (i = 0; i < n; i++)
    used[i] = i;
  for (i = n-1; i > 0; i--) {
    rnd = rand() % (i+1) ;
    j = used[i];  used[i] = used[rnd]; used[rnd] = j;
  }
}

search_used(int n) //n番目の囚人の戦略実行
{ 
  int i,j;
  j=n;
  for (i= 0; i < SIZE/2; i++) {
      if (used[j]==n) return 1;
      j = used[j];
  }
  return 0;
}

not_killed(int n) //n番目の囚人が失敗するか，成功するか？
{
   int i;
   for (i= 0; i < n; i++) {
       if (search_used(i)==0) return 0;
  }
  return 1;
}

int main(void)
{
  int i, n;
  srand((unsigned) time(NULL));
  for (n = 0, i = 0; i < NTRIALS; i++) {
    swapped(SIZE);
    if (not_killed(SIZE))
      n++;
  }
  printf("囚人の数=%d 釈放される確率= %.6lf\n", 
          SIZE, n * 1.0 / NTRIALS);
  return 0;
}