14079: 【原4079】扔气球

题目

题目描述

author: BowenTan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4079 时间限制：2s

Description

tbw买了很多气球，这些气球都是同款。他现在想借助一个n(1<=n<=10^18)层的高楼确定这款气球的硬度。（做这么蠢的事情，他应该是智商有猫饼）。

他还要你来给他做。

实验过程是这样的：每次你拿着一个气球爬到第f层楼，将它往地上扔。如果气球破了，说明他的硬度不超过f；如果没破，说明硬度至少为f。气球被摔过之后如果没破，那么硬度是不会变的。

给你k(1<=k<=100)个气球用来做实验（可以打破它们），你的任务是求出至少需要多少次实验，才能确定气球的硬度（或者得出结论：站在最高层也摔不破）。

input format

本题包含多组输入数据，数据开始首先输入数据组数T(T<=5)

每组数据包含两个数k, n，意义如题目描述。

output format

对于每一组输入，都输出最少的实验次数。

sample input

sample output

limits

对于10%的数据，k<=5, n<=5
对于20%的数据，k<=10, n<=1000
对于100%的数据，k<=100, n<=10^18

zqy2018's solution

/*
    Hint: see Leetcode 887
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int k;
unsigned long long n;
unsigned long long f[106][10005] = {0};
void init(){
    for (int i = 1; i <= 10000; ++i){
        for (int j = 1; j <= 100; ++j)
            f[j][i] = f[j - 1][i - 1] + 1 + f[j][i - 1];
    }
}
void solve(){
    scanf("%d%llu", &k, &n);
    int ans = 1;
    while (f[k][ans] < n)
        ++ans;
    printf("%d\n", ans);
}
int main(){
    int T = read();
    init();
    while (T--){
        solve();
    }
    return 0;
}