```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 ``` ```// 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 #include #include #include #include using namespace std; int memoitazation[501][501]; int findTestCount(int e, int f) { if(!memoitazation[e][f]) { int mn = numeric_limits::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::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; } ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ``` ```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 ```