結果

問題 No.2934 Digit Sum
ユーザー GOTKAKOGOTKAKO
提出日時 2024-10-13 16:29:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,582 bytes
コンパイル時間 2,131 ms
コンパイル使用メモリ 213,088 KB
実行使用メモリ 48,000 KB
最終ジャッジ日時 2024-10-13 16:29:31
合計ジャッジ時間 5,022 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
47,744 KB
testcase_01 AC 85 ms
47,744 KB
testcase_02 AC 65 ms
47,744 KB
testcase_03 AC 66 ms
47,872 KB
testcase_04 AC 65 ms
47,744 KB
testcase_05 AC 70 ms
47,744 KB
testcase_06 AC 67 ms
47,788 KB
testcase_07 AC 76 ms
47,616 KB
testcase_08 AC 74 ms
47,744 KB
testcase_09 WA -
testcase_10 AC 82 ms
48,000 KB
testcase_11 AC 87 ms
47,744 KB
testcase_12 AC 86 ms
47,744 KB
testcase_13 AC 88 ms
47,728 KB
testcase_14 AC 88 ms
47,616 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 89 ms
47,744 KB
testcase_18 AC 89 ms
47,744 KB
testcase_19 AC 93 ms
47,744 KB
testcase_20 AC 84 ms
47,744 KB
testcase_21 AC 85 ms
47,616 KB
testcase_22 AC 88 ms
47,744 KB
testcase_23 AC 87 ms
47,744 KB
testcase_24 AC 87 ms
47,616 KB
testcase_25 AC 86 ms
47,740 KB
testcase_26 AC 86 ms
47,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N,K; cin >> N >> K;
    if(N > 100000*9){cout << K << endl; return 0;}
    

    vector<vector<__int128_t>> dp(1000+1,vector<__int128_t>(171+1)),dp2 = dp;
    //1000C9->10^18以上,9*19.
    dp.at(0).at(0) = 1;
    for(int i=1; i<=1000; i++){
        for(int k=0; k<=171; k++){
            for(int l=max(k-9,0); l<=k; l++){
                if(l != k && dp2.at(i).at(k) != -1){
                    dp2.at(i).at(k) += dp.at(i-1).at(l);
                    if(dp.at(i-1).at(l) == -1 || dp2.at(i).at(k) > K) dp2.at(i).at(k) = -1;
                }
                dp.at(i).at(k) += dp.at(i-1).at(l);
                if(dp.at(i-1).at(l) == -1 || dp.at(i).at(k) > K){dp.at(i).at(k) = -1; break;}
            }
        }
    }

    int n = 100000;
    vector<vector<__int128_t>> dp3(n+1,vector<__int128_t>(10)),dp4 = dp3;
    dp3.at(0).at(0) = 1;
    for(int i=1; i<=n; i++){
        for(int k=0; k<=9; k++){
            for(int l=max(k-9,0); l<=k; l++){
                if(l != k && dp4.at(i).at(k) != -1){
                    dp4.at(i).at(k) += dp3.at(i-1).at(l);
                    if(dp3.at(i-1).at(l) == -1 || dp4.at(i).at(k) > K) dp4.at(i).at(k) = -1; 
                }
                dp3.at(i).at(k) += dp3.at(i-1).at(l);
                if(dp3.at(i-1).at(l) == -1 || dp3.at(i).at(k) > K){dp3.at(i).at(k) = -1; break;}
            }
        }
    }

    for(int i=0; i<=1000; i++){
        for(int k=1; k<=171; k++){
            if(dp.at(i).at(k) == -1) continue; 
            dp.at(i).at(k) += dp.at(i).at(k-1);
            if(dp.at(i).at(k-1) == -1 || dp.at(i).at(k) > K) dp.at(i).at(k) = -1;
        }
    }
    for(int i=0; i<=n; i++) for(int k=1; k<10; k++){
        if(dp3.at(i).at(k) == -1) continue;
        dp3.at(i).at(k) += dp3.at(i).at(k-1);
        if(dp3.at(i).at(k) > K || dp3.at(i).at(k-1) == -1) dp3.at(i).at(k) = -1;
    }
    for(int i=0; i<=n; i++) for(int k=1; k<10; k++){
        if(dp4.at(i).at(k) == -1) continue;
        dp4.at(i).at(k) += dp4.at(i).at(k-1);
        if(dp4.at(i).at(k) > K || dp4.at(i).at(k-1) == -1) dp4.at(i).at(k) = -1;
    }

    N = min(N,171LL);
    string answer = "";
    if(N < 10){
        int digit = 0;
        long long all = 0;
        for(int i=0; i<=n; i++){
            all += dp4.at(i).at(N);
            if(all > K || dp4.at(i).at(N) == -1){digit = i; break;}
        }
        for(int i=digit; i>=0; i--){
            int d = 0;
            for(int k=0; k<=N; k++){
                int left = N-k;
                __int128_t now = dp3.at(i).at(left);
                if(now > K || now == -1){N -= d; answer += '0'+d; break;}
                K -= now; d++;
            }
        }
    }
    else{
        int digit = 0;
        long long all = 0;
        for(int i=0; i<=1000; i++){
            all += dp2.at(i).at(N);
            if(all > K || dp2.at(i).at(N) == -1){digit = i; break;}
        }
        for(int i=digit; i>=0; i--){
            for(int k=0; k<=min(N,9LL); k++){
                int left = N-k;
                __int128_t next = dp.at(i).at(left);
                if(next == -1){N -= k; answer += '0'+k; break;}
                if(next > K){
                    answer += '0'+k; N -= k;
                    break;
                }
                K -= dp.at(i).at(left);
            }
        }
    }
    reverse(answer.begin(),answer.end());
    while(answer.back() == '0') answer.pop_back();
    reverse(answer.begin(),answer.end());
    cout << answer << endl;
}
0