题目地址：ZCMU：Power Eggs

题目描述

Benedict bought K identical power eggs from Dropeggs.com, and now he wants to test them by dropping them from different floors of his building. His building has N floors numbered 1 to N. F is an unknown number in the range from 0 to N, inclusive. Each egg will break if dropped from floor F+1 or above, but will not break if dropped from floor F or below. Benedict can drop each egg as many times as he wants from any floor until it breaks. He wants to know the minimum number of egg drops necessary to ensure that he can determine F.
For example, if there are three floors and Benedict has only one egg, then he has to first throw the egg from the first floor, then from the second floor (if the egg survived), and then from the third floor (if the egg survived). Therefore, three drops are required in the worst case.
有K个鹰蛋N层楼，鹰蛋从1~F层楼掉下来不会碎，F+1层及以上掉下来会碎，要求求确定F值最坏情况下的最小值。

输入输出格式

输入格式：
The first line contains one number T (1 ≤ T ≤ 10000) which is the number of test cases, followed by T lines. Each of the next T lines contains two numbers: N, the number of floors (1 ≤ N ≤ 2000000007) and K, the number of eggs (1 ≤ K ≤ 32).

输出格式：
For each of the T lines, print the minimal number of drops required, or if it’s greater than 32, print the word Impossible. After that many drops, Benedict gets too tired and cannot continue.

输入输出样例

输入样例#1：

4
10 1
100 2
30 30
2000000000 2

输出样例#1：

10
14
5
Impossible

题解

其实把这个题放在这最重要的不是这个题，而是下面这个ppt的内容。
算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》.ppt
好的我们来说一下这题最后的解法。DP状态是dp[i][j]表示i个鹰蛋尝试j次最多能确定几层楼的情况。转移方程如下
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1
如果这颗蛋碎了，剩下的蛋能确定的层数是第一项，如果没碎则是第二项。
初始值dp[1][j]=1，dp[i][1]=i。
对于可以交的这个题来说，预处理出32个蛋32次就可以做了。因为DP值具有单调性，甚至可以二分找到答案。
所以说这个题的意义不是去AC它，而是看上面那个PPT的内容啊！
如果是个老实的DP题，算法复杂度O(n \log n)

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 35;

int T;
LL n, k, dp[MAXN][MAXN];

int main() {
    for(int i = 1; i <= 32; i++) {
        dp[1][i] = i;
        dp[i][1] = 1;
    }
    for(int i = 2; i <= 32; i++) {
        for(int j = 2; j <= 32; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1;
        }
    }
    T = readint();
    while(T--) {
        n = readint();
        k = readint();
        int res = std::lower_bound(dp[k] + 1, dp[k] + 33, n) - dp[k];
        if(res > 32) printf("Impossible\n"); else printf("%d\n", res);
    }
    return 0;
}