The Two Egg Problem

eggs.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>

struct State
{
	int answer;
	int where;
	bool calculated;
	State() : answer(0), where(0), calculated( false ) {}
};

int eggs( std::vector< State >& t, int total )
{
	if ( t[total].calculated )
	{
		return t[total].answer;
	}

	int best = total + 1;
	int where = 1;
	for ( int i = 1; i <= total; i++ )
	{
		int current = 1 + std::max( i - 1, eggs( t, total - i ) );
		if ( current < best )
		{
			best = current;
			where = i;
		}
	}

	t[total].answer = best;
	t[total].where = where;
	t[total].calculated = true;
	return best;
}

int main()
{
	int total = 100;
	std::vector< State > t( total + 1 );
	int ans = eggs( t, total );
	printf( "%d\n", ans );

	int floors = total;
	int w = 0;
	while ( floors > 0 )
	{
		w += t[ floors ].where;
		printf("%d ", w );
		floors = floors - t[ floors ].where;
	}
	printf("\n");

	return 0;
}