QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253535#6558. Allergen TestingNicolas125841WA 3ms3980kbC++171.6kb2023-11-17 07:35:392023-11-17 07:35:40

Judging History

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

  • [2023-11-17 07:35:40]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3980kb
  • [2023-11-17 07:35:39]
  • 提交

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 = 61;
    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(61, 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;
    int cnt = 1;

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

        if(cnt == 20)
            cout << n << " " << d << "\n"; 

        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) >= n){
                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: 3980kb

input:

1
4 1

output:

2

result:

ok single line: '2'

Test #2:

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

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
60
0
1
2
2
2
3
2
2
2
3
2
2
2
3
2
2
2
4
2
2
2
3
2
2
2
3
2
2
2
4
2
2
2
4
2
2
2
4
2
2
2
3
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
6
4
4
4
4
4
4
4
4
4
4...

result:

wrong answer 20th lines differ - expected: '3', found: '4'