input
T 1<=T<=10000
n m 1<=n<=2000000007 1<=m<=32
output
m个鸡蛋从1到n哪一楼x扔下去刚好没碎，而再x+1楼扔下去就碎了，求最少扔的次数无论x为1到n的哪个数都能确定x
如果x>32,输出Impossible，否则输出x
做法：dp，d(x,y)=d(x,y-1)+d(x-1,y-1),x:egg,y:floor求出下限，即x个鸡蛋至少要试多少次
# include <stdio.h>
# include <limits.h>
#define INF 2000000010
int max(int a, int b) { return (a > b)? a: b; }
int eggFloor[][];
int eggDrop(int n, int k)
{
/* eggFloor[i][j] 表示对于 i个鸡蛋 j 层楼，需要的最少测试次数 */
int res;
int i, j, x;
// 初始化
for (i = ; i <= n; i++)
{
eggFloor[i][] = ;
eggFloor[i][] = ;
} //只有一个鸡蛋，没得优化，需要j次
for (j = ; j <= k; j++)
eggFloor[][j] = j; // 最优子结构的递推
for (i = ; i <= n; i++)
{
for (j = ; j <= k; j++)
{
eggFloor[i][j] = INT_MAX;
for (x = ; x <= j; x++)
{
res = + max(eggFloor[i-][x-], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
}
int a[][][];
int init()
{
for(int i=;i<=;i++) { a[][i][]=a[][i][]=;a[][i][]=a[][i][]=; }
for(int j=;j<=;j++) a[][][j]=a[][][j]=j;
for(int i=;i<=;i++)//egg
{
for(int j=;j<=;j++)//floor
{
a[][i][j]=a[][i][j-]+;
a[][i][j]=a[][i][j]+a[][i-][j-];
if(a[][i][j]<) a[][i][j]=INF;
if(a[][i][j]<) a[][i][j]=INF;
}
}
for(int i=;i<=;i++,printf("\n"))
for(int j=;j<=;j++)
printf("%2d,%2d ",a[][i][j],a[][i][j]);
}
int b[][];
int init1()
{
for(int i=;i<=;i++) { b[i][]=;b[i][]=; }
for(int j=;j<=;j++) b[][j]=j;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
b[i][j]=+b[i][j-]+b[i-][j-];
if(b[i][j]<) b[i][j]=INF;
}
}
/* for(int i=1;i<=33;i++,printf("\n"))
for(int j=1;j<=33;j++)
printf("%d ",b[i][j]);*/
}
/* 测试*/
int main()
{
// freopen("out","w",stdout);
// init();
init1();
int n,k,i,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(i=;i<=;i++) if(n<=b[k][i]) break;
i<=?printf("%d\n",i):puts("Impossible");
}
return ;
eggDrop(n,k);
for(int i=;i<=n;i++)//egg
{
for(int j=;j<=k;j++) printf("%2d ",eggFloor[i][j]);
printf("\n");
}
return ;
}