#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int random(int n)
{
	int r = rand();
	int r2 = r + (r >> 7) + (r >> 13);
	return r2 % n;
}

#define SIZE 100

int maze[SIZE][3];
int L[SIZE*3];
int R[SIZE*3];
bool end[SIZE*3];

#define UNDEFINED -1

void generate_maze(int n)
{
	for (int i = 0; i < n; i++)
	{
		maze[i][0] = UNDEFINED;
		maze[i][1] = UNDEFINED;
		maze[i][2] = UNDEFINED;
	}
	
	// make first connection
	{
		maze[0][0] = 0;
		
		int k = random(n);
		if (k == 0)
			maze[0][1] = 1;
		else
			maze[1][0] = 1;
	}
	
	int l = 1;
	for (int empty_places = n * 3 - 2; empty_places > 0;)
	{
		// find a node with a free place
		int i1, j1;
		for (i1 = 0; i1 < n; i1++)
			if (maze[i1][0] != UNDEFINED && maze[i1][2] == UNDEFINED)
				break;
		if (maze[i1][1] == UNDEFINED)
			j1 = 1;
		else
			j1 = 2;
		maze[i1][j1] = 2*l;
		//printf("maze[%d][%d] = %d ", i1, j1, l);
			
		// find another node with
		int i2, j2;
		do
		{
			i2 = random(n);
			//printf(" i2 = %d ", i2);
		} while (maze[i2][2] != UNDEFINED);
		while (maze[i2][0] == UNDEFINED && maze[i2-1][0] == UNDEFINED)
			i2--;
		
		if (maze[i2][0] == UNDEFINED)
			j2 = 0;
		else if (maze[i2][1] == UNDEFINED)
			j2 = 1;
		else
			j2 = 2;
		maze[i2][j2] = 2*l + 1;
		//printf(" maze[%d][%d] = %d ", i2, j2, l);
		
		//printf("e = %d ", empty_places);
		if (empty_places == 2)
			break;
			
		bool can_go_next = false;
		for (int i = 0; i < n; i++)
			if (maze[i][0] != UNDEFINED && maze[i][2] == UNDEFINED)
			{
				can_go_next = true;
				break;
			}
		
		if (!can_go_next)
		{
			//printf(" go back\n");
			maze[i1][j1] = UNDEFINED;
			maze[i2][j2] = UNDEFINED;
		}
		else
		{
			//printf(" okay\n");
			empty_places -= 2;
			l++;
		}
	}
	
	for (int i = 1; i < n; i++)
	{
		if (random(2) == 1)
		{
			int h = maze[i][1];
			maze[i][1] = maze[i][2];
			maze[i][2] = h;
		}
	}
}

void print_maze(int n)
{
	for (int i = 0; i < n; i++)
		printf("%2d %2d %2d\n", maze[i][0]/2, maze[i][1]/2, maze[i][2]/2);
	printf("\n");
}

int reverse(int i)
{
	return (i & ~1) | (~i & 1);
}

void fill_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		int v0 = maze[i][0];
		int v1 = maze[i][1];
		int v2 = maze[i][2];
		int w0 = reverse(v0);
		int w1 = reverse(v1);
		int w2 = reverse(v2);
	
		L[v0] = w1;
		L[v1] = w2;
		L[v2] = w0;
		
		R[v0] = w2;
		R[v1] = w0;
		R[v2] = w1;
	}

	for (int i = 0; i < n*3; i++)
		end[i] = false;
	end[maze[0][0]] = true;		
	end[maze[0][1]] = true;		
	end[maze[0][2]] = true;		
}

void check_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		if (   reverse(L[reverse(R[i])]) != i
		    || reverse(R[reverse(L[i])]) != i
		    || reverse(L[reverse(L[reverse(L[i])])]) != i
		    || reverse(R[reverse(R[reverse(R[i])])]) != i)
		    printf("error %d\n", i);
	}
}

void print_LR(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%2d: %2d %2d %s\n", i, L[i], R[i], end[i] ? "end" : "");
	}
	printf("\n");
}

int min[SIZE*3];

void print_LR_min(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%2d (%2d): %2d (%d)  %2d (%d)\n", i, min[i], L[i], min[L[i]], R[i], min[R[i]]);
	}
	printf("\n");
}

void calculate_min(int n)
{
	for (int i = 0; i < n; i++)
		min[i] = end[i] ? 0 : n;

	for (bool modified = true; modified;)		
	{
		//print_LR_min(n);
		//printf("--\n");
		modified = false;
		for (int j = 0; j < n; j++)
		{
			int m = min[L[j]] + 1;
			if (m < min[j])
			{
				min[j] = m;
				modified = true;
			}
			m = min[R[j]] + 1;
			if (m < min[j])
			{
				min[j] = m;
				modified = true;
			}
		}
	}
}

class Stat
{
public:
	Stat() : n(0), _sum(0.0), _sum2(0.0) {}
	void add(double v)
	{
		if (n == 0 || v < min)
			min = v;
		if (n == 0 || v > max)
			max = v;
		n++;
		_sum += v;
		_sum2 += v*v;		
	}
	double average()
	{
		if (n == 0)
			return 0.0;
		return _sum / n;
	}
	double stddev()
	{
		if (n <= 1)
			return 0.0;
		return sqrt((_sum2 - _sum*_sum/(double)n) / (double)(n));
	}
	
	void print()
	{
		printf("[%lf %lf %lf] %lf", min, average(), max, stddev());
	}
	
	long n;
	double min;
	double max;
	
private:
	double _sum;
	double _sum2;
};

void solve_straight(int n, long &depth, long &underway)
{
	int pos[3*SIZE];
	
	for (int i = 0; i < n; i++)
		pos[i] = i;

	depth = 0;
	underway = 0;
	for (;depth < 300;)
	{
		// Count number at end position
		int at_end = 0;
		for (int i = 0; i < n; i++)
			if (end[pos[i]])
				at_end++;
		if (at_end == n)
			break; // -- we are done

		depth++;
		underway += n - at_end;
		
		// Evaluate left and right
		int min_L = n;
		int nr_at_min_L = 0;
		int left_L = 0;
		double cost_L = 0.0;
		int min_R = n;
		int nr_at_min_R = 0;
		int left_R = 0;
		double cost_R = 0.0;
		for (int i = 0; i < n; i++)
			if (!end[pos[i]])
			{
				int m = min[L[pos[i]]];
				if (m < min_L)
				{
					min_L = m;
					nr_at_min_L = 1;
				}
				else if (m == min_L)
					nr_at_min_L++;
				left_L += m;
				cost_L += sqrt(sqrt(m));
				m = min[R[pos[i]]];
				if (m < min_R)
				{
					min_R = m;
					nr_at_min_R = 1;
				}
				else if (m == min_R)
					nr_at_min_R++;
				left_R += m;
				cost_R += sqrt(sqrt(m));
			}

#define SMALLER(X,Y) (X) < (Y) ? true : (X) > (Y) ? false :
#define SELECT(Z) if (Z random(2) == 0)
		// make selection
//		SELECT(SMALLER(min_L, min_R))
//		SELECT(SMALLER(min_L, min_R) SMALLER(left_L, left_R))
//		SELECT(SMALLER(min_L, min_R) SMALLER(nr_at_min_R, nr_at_min_L))
//		SELECT(SMALLER(cost_L, cost_R))
		SELECT(SMALLER(min_L, min_R) SMALLER(cost_L, cost_R))
		{
			//printf("L");
			for (int i = 0; i < n; i++)
			{
				if (!end[pos[i]])
					pos[i] = L[pos[i]];
				//printf(" %2d", pos[i]);
			}
		}	
		else
		{
			//printf("R");
			for (int i = 0; i < n; i++)
			{
				if (!end[pos[i]])
					pos[i] = R[pos[i]];
				//printf(" %2d", pos[i]);
			}
		}
		//printf("\n");
	}

	//printf("%ld %lf\n", depth, ((double)underway)/(double)n);
}

#define WORKSET_SIZE 1000
struct State
{
	int pos[3*SIZE];	
	int underway;
	int min;
	int nr_at_min;
	int left;
	double cost;
};

State state_workset[WORKSET_SIZE];
State* free_states[WORKSET_SIZE];
int nr_free_states = 0;
State* old_states[WORKSET_SIZE];
int nr_old = 0;
State* new_states[WORKSET_SIZE];
int nr_new = 0;

State* alloc_state()
{
	if (nr_free_states > 0)
		return free_states[--nr_free_states];
	
	if (nr_new > nr_old)
		return new_states[--nr_new];
	else
		return old_states[--nr_old];
}

void dealloc_state(State* state)
{
	free_states[nr_free_states++] = state;
}

void insert_in_new_states(State* state)
{
	for (int i = 0; i < nr_new; i++)
	{
//		SELECT(SMALLER(state->min, new_states[i]->min))
//		SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->left, new_states[i]->left))
//		SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->nr_at_min, new_states[i]->nr_at_min))
//		SELECT(SMALLER(state->cost, new_states[i]->cost))
		SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->cost, new_states[i]->cost))
		{
			State* h = new_states[i];
			new_states[i] = state;
			state = h;
		}
	}
	
	if (nr_new < WORKSET_SIZE)
	{
		new_states[nr_new++] = state;
	}
	else
		dealloc_state(state);
}


void solve_with_workset(int n, long &depth, long &underway)
{
	for (int i = 0; i < WORKSET_SIZE; i++)
		free_states[i] = &state_workset[i];
	nr_free_states = WORKSET_SIZE;		
	
	// Initialize
	State* init_state = alloc_state();
	init_state->left = 0;
	for (int i = 0; i < n; i++)
	{
		init_state->pos[i] = i;
		if (!end[i])
			init_state->left++;
	}
	init_state->underway = init_state->left;
	old_states[0] = init_state;
	nr_old = 1;
	
	// Iterate
	for(depth = 1; ; depth++)
	{
		for(int i = 0; i < nr_old; i++)
		{
			State* old_state = old_states[i];
			if (old_state->left == 0)
			{
				underway = old_state->underway;
				return;				
			}
			State* new_state_L = alloc_state();
			if (new_state_L == old_state)
			{	dealloc_state(old_state);
				break;
			}
			State* new_state_R = alloc_state();
			if (new_state_R == old_state)
			{	dealloc_state(new_state_R);
				dealloc_state(old_state);
				break;
			}

			// Evaluate left and right
			new_state_L->underway = old_state->underway;
			new_state_L->min = n;
			new_state_L->nr_at_min = 0;
			new_state_L->left = 0;
			new_state_L->cost = 0.0;
			new_state_R->underway = old_state->underway;
			new_state_R->min = n;
			new_state_R->nr_at_min = 0;
			new_state_R->left = 0;
			new_state_R->cost = 0.0;
			for (int j = 0; j < n; j++)
			{
				int pos = old_state->pos[j];
				if (!end[pos])
				{
					new_state_L->pos[j] = L[pos];
					int m = min[L[pos]];
					if (m < new_state_L->min)
					{
						new_state_L->min = m;
						new_state_L->nr_at_min = 1;
					}
					else if (m == new_state_L->min)
						new_state_L->nr_at_min++;
					new_state_L->underway++;
					new_state_L->left += m;
					new_state_L->cost += sqrt(sqrt(m));

					new_state_R->pos[j] = R[pos];
					m = min[R[pos]];
					if (m < new_state_R->min)
					{
						new_state_R->min = m;
						new_state_R->nr_at_min = 1;
					}
					else if (m == new_state_R->min)
						new_state_R->nr_at_min++;
					new_state_R->underway++;
					new_state_R->left += m;
					new_state_R->cost += sqrt(sqrt(m));
				}
				else
				{
					new_state_L->pos[j] = pos;
					new_state_R->pos[j] = pos;
				}
			}	
			new_state_L->underway = old_state->underway + new_state_L->left;
			new_state_R->underway = old_state->underway + new_state_R->left;
			insert_in_new_states(new_state_L);
			insert_in_new_states(new_state_R);		
			
			dealloc_state(old_state);
		}
		
		for (int i = 0; i < nr_new; i++)
			old_states[i] = new_states[i];
		nr_old = nr_new;
		nr_new = 0;
	}
}

int main(int argc, char *argv[])
{
	srand(time(0));

	for (int n = 10; n < 100; n += 2)
	{

		Stat depth_stat;
		Stat underway_stat;
		
		for (int times = 0; times < 100; times++)
		{
			generate_maze(n);
			//print_maze(n);
			fill_LR(n);
			int n3 = n * 3;
			check_LR(n3);
			//print_LR(n3);
			calculate_min(n3);
			//print_LR_min(n3);
		
#ifdef STRAIGHT		
			for (int x = 0; x < 100; x++)
			{
				long depth;
				long underway;
				solve_straight(n, depth, underway);
				
				depth_stat.add(depth);
				underway_stat.add((double)underway/(double)n);
				
			}
#else
			long depth;
			long underway;
			solve_with_workset(n, depth, underway);
			depth_stat.add(depth);
			underway_stat.add((double)underway/(double)n);
#endif
		}
		printf("%3d: depth: ", n); depth_stat.print();
		printf(" underway: "); underway_stat.print();
		printf("\n");
	}
	return 0;
}