QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253532#6558. Allergen TestingNicolas125841WA 3ms3540kbC++171.5kb2023-11-17 07:29:102023-11-17 07:29:10

Judging History

你现在查看的是最新测评结果

  • [2023-11-17 07:29:10]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3540kb
  • [2023-11-17 07:29:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    const int maxn = 60;
    ll C[maxn + 1][maxn + 1];
    C[0][0] = 1;
    for (int n = 1; n <= maxn; ++n) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k)
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }

    vector<vector<ll>> dp(60, vector<ll>(1000, 0));

    for(int i = 0; i < 1000; i++)
        dp[0][i] = 1;

    for(int i = 1; i < 60; i++){
        dp[i][0] = 1; 

        for(int j = 1; j < 1000; j++)
            for(int k = 0; k <= i; k++)
                dp[i][j] += C[i][k] * dp[i - k][j - 1];
    }

    int t;
    cin >> t;

    while(t--){
        ll n, d;
        cin >> n >> d;

        if(d < 1000){
            for(int i = 0; i < 60; i++){
                if(dp[i][d] >= n){
                    cout << i << "\n";
                    break;
                }
            }
        }else{
            if(1 >= n){
                cout << "0\n";
            }else if(d + 1 >= n){
                cout << "1\n";
            }else if((d + 1) * (d + 1)){
                cout << "2\n";
            }else if(d + 1 + 3 * d * (d + 1) / 2 + d * (2 * d + 1) * (d + 1) / 2 >= n){
                cout << "3\n";
            }else{
                cout << "4\n";
            }
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3520kb

input:

1
4 1

output:

2

result:

ok single line: '2'

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3540kb

input:

10000
1 1
1000000000000000000 1
1 1000000000000000000
1000000000000000000 1000000000000000000
26615519354743225 163142634
26615519354743225 163142634
26615519354743224 163142634
26615519354743226 163142634
847997831064072529 920867976
847997831064072529 920867976
847997831064072528 920867976
8479978...

output:

0
0
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
5
5
5
6
2
2
2
2
2
2
2
2
2
2
2
...

result:

wrong answer 2nd lines differ - expected: '60', found: '0'