/* * Solution for One-person "Price is Right" * * The basic idea is to use dynamic programming. Let * * N(G,L) = max range that can be searched with G guesses and L lifelines * left. * * Then we have the following recurrence: * * N(0,L) = 0 for all L (no guess => lose) * N(G,0) = G for all G (no more lifelines, can only do 1, 2, ..., G) * N(G,L) = N(G-1,L-1) + 1 + N(G-1, L) for G, L >= 1 * * This means: guess some price P (accounts for +1) * if it's too high, then we can cover N(G-1,L-1) below P * if it's too low, then we can cover N(G-1,L) above P * */ #include #define MAX_G 30 #define MAX_L 30 int solve(int G, int L) { int N[MAX_G+1][MAX_L+1]; int g, l; for (l = 0; l <= L; l++) { N[0][l] = 0; } for (g = 0; g <= G; g++) { N[g][0] = g; } for (g = 1; g <= G; g++) { for (l = 1; l <= L; l++) { N[g][l] = N[g-1][l-1] + 1 + N[g-1][l]; } } return N[G][L]; } int main(void) { int G, L; int case_no = 1; while (scanf("%d %d", &G, &L) == 2 && (G || L)) { printf("Case %d: %d\n", case_no++, solve(G,L)); } return 0; }