/* 

Consider a loop of string of unit length. Suppose we cut the string independently and at random in n places. This will divide the loop into n pieces.

1. What is the expected (average) size of the smallest piece?
2. What is the expected (average) size of the largest piece?
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <vector>
#include <time.h>
#include <stdio.h>
#define M		50000

using namespace std;
typedef vector<double> vd;
typedef ostream_iterator<double> od;

int main(int argc, char* argv[])
{
	srand(time(NULL));
	double r;
	long j = 0;

	if (argc!=2) {return 1;}
	int N = atoi(argv[1]);
	cout.precision(10);
	cout << "Cut the loop string to " << N << " pieces ...\n";
	vd randl, maxl, minl;
	od out(cout, "  ");

	for (int i=0; i<M; i++){
		randl.clear();
		vd pcl(N);
		for (int j=0; j<N-1; j++){
			r = (double)rand()/(double)(RAND_MAX);
			randl.push_back(r);
		}
		randl.push_back(1);
		sort(randl.begin(), randl.end());
		//copy(randl.begin(), randl.end(), out);
		//cout << endl;
		adjacent_difference(randl.begin(), randl.end(), pcl.begin());
		double max = *(max_element(pcl.begin(), pcl.end()));
		double min = *(min_element(pcl.begin(), pcl.end()));
		maxl.push_back(max);
		minl.push_back(min);
		printf("o Progress [== %4.2f %% ==]\r", (double)(j++/(double)M)*100.0); 
	}
	cout << "----------------------------------\n";
	double max_strip = accumulate(maxl.begin(), maxl.end(), (double)0)/(double) maxl.size();
	double min_strip = accumulate(minl.begin(), minl.end(), (double)0)/(double) minl.size();
	cout << "E(max) = " << max_strip << endl;
	cout << "E(min) = " << min_strip << endl;

	return 0;
}