U4699 鸡蛋

题目背景

调皮的kkk准备恶搞他的同学兼朋友——你！

题目描述

kkk准备从楼上扔鸡蛋下来砸在lzn身上，让lzn变成“鸡蛋王子”。但是如果鸡蛋没有破裂，辣么就没有什么好玩的了，所以kkk必须知道鸡蛋最少在哪一层楼上扔下来会摔破。

kkk为了实验事先买了K个鸡蛋（这些鸡蛋的硬度一样），并来到了一个N层高楼上。每次kkk可以拿着一个鸡蛋从t楼扔下去，并观察鸡蛋有没有摔破。如果鸡蛋在第t层楼没有摔破，那么在1..t-1层楼都不会摔破，而且不论在1..t层楼摔多少次鸡蛋都不会破。

lzn马上就要过来了，所以你需要帮kkk求出，她最少要做多少次实验。

输入输出格式

有多组数据，每组数据包含两个整数K和N

对于每组数据输出最少实验次数，如果实验63次还不能成功，输出TLE

输入输出样例

2 1001 100

14TLE

说明

1<=K<=100

1<=N<2^64

题解：

数据范围太大，二分就拜拜了。

只能用考虑dp or递推。

然后自己软腿就推出来了。

f[i][j]表示i个鸡蛋扔j次恰好是f[i][j]层随

转移f[i][j]=f[i][j-1]+f[i-1][j-1]+1;

AC代码：

#include<iostream>#include<cstdio>using namespace std;long long f[105][3001];long long k,n;int main(){    for(int a=1;a<=101;a++)        for(int b=1;b<=3000;b++)            f[a][b]=f[a][b-1]+f[a-1][b-1]+1;    while(cin>>k>>n){        bool flag=0;        for(int a=0;a<=63;a++) if(f[k][a]>=n){            flag=1;            printf("%d\n",a);            break;        }        if(!flag) printf("TLE\n");    }    return 0;}