题意：n层楼楼房，有K个水球，每个水球都有一个相同的扛摔系数。即从某层楼高及其以下的楼层摔下不会坏，而从其以上的楼层摔下会坏。问：最少需要多少次尝试能够求得扛摔系数

 

更简单的抽象：现在有一个未知数X，范围在1-n内。现在需要猜至少多少次Y，返回的结果是Y<X或Y>X或Y=X，则可以求出X

我们定义dp[i]为：猜测 i 次后能够得到的最大区间

那么有如下几种情况：

A：第 i 次返回Y<X，这种情况对dp[i]的贡献为：dp[i-1]

B：第 i 次返回Y>X，这种情况对dp[i]的贡献为：dp[i-1]

C：第 i 次返回Y=X，这种情况对dp[i]的贡献为：1

所以，dp[i] = 2 * dp[i-1] + 1

 

根据上述，定义dp[i][j]为猜测 i 次，得到 j 次 Y>X 回答后游戏结束时，能够得到的最大区间

即有：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + 1

要求的答案为：dp[i][k] >= n中的最小的 i

 

一开始觉得可能会有精度问题：如果在某个加法过程中越界long long会怎么样，又没法知道那么大数据的结果是否正确，但是样例有两个这种大数据避免了这个想法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstdlib>
using namespace std;

long long n,dp[150][150];

int main()
{
    int i,j,k;
    while(scanf("%d%lld",&k,&n)&&k){
        memset(dp,0,sizeof(dp));
        int flag=0;
        for(i=1;i<=63;i++){
            for(j=1;j<=k;j++)
                dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1;
            if (dp[i][k]>=n){
                flag=1;
                break;
            }
        }
        if (flag)
            printf("%d\n",i);
        else
            puts("More than 63 trials needed.");
    }
    return 0;
}