Skip to content

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

4
1 10
2 10
2 100
10 786599

sample output

10
4
14
21

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;
}