// Problem statement: Find the minimum number of tests required to
// determine the lowest floor in a building from which when we drop
// an egg it should _NOT_ break.
//
// - An egg that survives a fall can be used again.
// - A broken egg must be discarded.
// - The effect of a fall is the same for all eggs.
// - If an egg breaks when dropped from a floor, then it would break
//   if dropped from a higher window.
// - If an egg survives a fall then it would survive a shorter fall.
// - It is not ruled out that the first-floor windows break eggs, nor is it
//   ruled out that the highest-floor windows do not cause an egg to break.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <limits>
using namespace std;

int memoitazation[501][501];

int findTestCount(int e, int f)
{
  if(!memoitazation[e][f]) {
    int mn = numeric_limits<int>::max();
    for(int i = 1; i <= f; ++i) {
      const int k = 1 + max( findTestCount(e-1, i-1), findTestCount(e, f-i) );
      mn = min(mn, k);
    }
    memoitazation[e][f] = 1 + mn;
  }
  return memoitazation[e][f] - 1;
}

void test_case(int e, int f)
{
  assert(e <= 500);
  assert(f <= 500);
  cout << "Number of eggs: " << e
       << ", number of floors: " << f << endl;
  cout << "Number of test cases: " << findTestCount(e, f) << endl;
  cout << endl;
}

void init()
{
  for(int i = 0; i <= 500; ++i) memoitazation[i][0] = 1;
  for(int i = 1; i <= 500; ++i) {
    memoitazation[0][i] = numeric_limits<int>::max();
    memoitazation[1][i] = 1 + i;
  }
}

int main()
{
  init();
#define TEST(NUM_OF_EGGS,NUM_OF_FLOORS) test_case(NUM_OF_EGGS,NUM_OF_FLOORS)
  TEST(2, 100);
  TEST(3, 100);
  TEST(3, 200);
  TEST(99, 64);
  TEST(50, 500);
  return 0;
}

Number of eggs: 2, number of floors: 100
Number of test cases: 14

Number of eggs: 3, number of floors: 100
Number of test cases: 9

Number of eggs: 3, number of floors: 200
Number of test cases: 11

Number of eggs: 99, number of floors: 64
Number of test cases: 7

Number of eggs: 50, number of floors: 500
Number of test cases: 9