#include <iostream>
#include <fstream>
#include <algorithm>

int myrand() {
	static std::ifstream f("/dev/urandom");

	for(;;) {
		unsigned char c;
		f >> c;

		if(c < 100) {
			return c;
		} else if(c < 200) {
			return c - 100;
		}
	}
}

int main() {
	int successes = 0;

	for(int i = 0; i < (1 << 30); ++i) {
		int drawers[100];
		for(int j = 0; j < 100; ++j) {
			drawers[j] = j;
		}

		// knuth shuffle
		for(int j = 0; j < 100; ++j) {
			std::swap(drawers[j], drawers[myrand()]);
		}

		bool alive = true;

		// for every prisoner
		for(int j = 0; j < 100; ++j) {
			int current_drawer = j;

			bool success = false;

			for(int k = 0; k < 50; ++k) {
				current_drawer = drawers[current_drawer];

				if(current_drawer == j) {
					success = true;
					break;
				}
			}

			if(!success) {
				alive = false;
				break;
			}
		}

		if(alive) {
			++successes;
		}

		if(((i + 1) & ((1 << 20) - 1 )) == 0) {
			std::cerr << "#iter: " << (i + 1) << " alive: " << successes << " (" << ((double)successes / (i + 1) * 100) << "%" << std::endl;
		}
	}
}