codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// 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; }
Private
[
?
]
Run code
Submit