http://acm.pku.edu.cn/JudgeOnline/problem?id=1243
Код:
/*
* 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 <stdio.h>
#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;
}