# Random World

/**
 * 10000명의 사람, 2500개의 일이 있고, 일에 대한 능력치는 수치화 시킬 수 있으며 다른 사람과 겹치지 않는다.
 * 10000명의 사람은 각기 다른 능력치를 “랜덤”으로 부여 받으며, “랜덤”으로 1 ~ 50명을 알고지내는지 정해진다.
 * 이 경우 명제가 성립할 확률은 몇 % 인가?
 */

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <random>
#define N 10000
#define M 2500
#define F_MAX 50

using namespace std;
class Person {
public:
  int friends; // 알고 지내는 사람 수
  short *frineds_list; // 알고 지내는 사람들 리스트
  Person() {
    this->friends = rand() % 50 + 1;
    this->frineds_list = (short *) calloc(this->friends, sizeof(short));
  }
};

int main() {
  // random seed 초기화
  srand((unsigned int)time(NULL));

  // 능력치 설정 - stats[i] 는 i번째 사람의 0~2499번째 능력치
  vector<vector<short> > stats(N, vector<short>(M, 0));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      stats[i][j] = j;
    }
    random_shuffle(stats[i].begin(), stats[i].end());
  }

  // 친구 설정
  vector<short> friends_id(N, 0);
  for (int i = 0; i < N; i++) {
    friends_id[i] = i;
  }
  
  // 10000명에 대하여 능력치와 알고 지내는 사람 수 세팅 (월드 생성)
  vector<Person> people(N);
  for (int i = 0; i < N; i++) {
    Person p;
    
    people[i] = p;
    random_shuffle(friends_id.begin(), friends_id.end());
    for (int j = 0; j < p.friends; j++) {
      p.frineds_list[j] = friends_id[j];
    }
  }

  // 확률 계산
  int learn_something_from_everybody = 0;
  for (int i = 0; i < N; i++) {
    int me = i;
    int learn_count = 0;
    int friends_number = people[i].friends;

    for (int j = 0; j < friends_number; j++) {
      int my_friend = people[i].frineds_list[j];
      bool can_learn_something = false;
      for (int k = 0; k < M; k++) {
        if (stats[my_friend][k] > stats[me][k]) {
          can_learn_something = true;
          break;
        }
      }

      if (can_learn_something) {
        learn_count ++;
      }
    }

    if (learn_count == friends_number) learn_something_from_everybody++;

  }

  cout << (double) learn_something_from_everybody / N << endl;

}