1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int simulate(const int& n){
	std::set<int> free;
	std::vector<int> arrival_order;

	int drunk = rand() % n;

	for (int i = 0; i < n; i++) {
		free.insert(i);
		if ( i != drunk )
			arrival_order.push_back(i);
	}

	std::random_shuffle(arrival_order.begin(), arrival_order.end());

	int drunk_seat = rand() % n;
	
	std::set<int>::iterator it = free.find(drunk_seat);
	free.erase(it);

	for (int i = 0; i < arrival_order.size(); i++){
		it = free.find(arrival_order[i]);
		if ( it == free.end() ){
			int x = rand() % free.size();
			it = free.begin();
			for (int j = 0; j < x; j++) ++it;
			free.erase(it);
		}
		else {
			free.erase(it);
			if ( i + 1 == arrival_order.size() )
				return 1;
		}
	}

	return 0;
}

int main(){
	int n, limit;
	srand(time(0));
	std::cout << "Number of people:";
	std::cin >> n;
	std::cout << "Number of iterations:";
	std::cin >> limit;

	int good = 0;
	for (int i = 0; i < limit; i++){
		good += simulate(n);
	}

	std::cout << good << " / " << limit << " = " << 1.0 * good / limit << std::endl;

	return 0;
}