結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー t98slider
提出日時 2023-02-21 07:17:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,356 bytes
コンパイル時間 1,677 ms
コンパイル使用メモリ 170,500 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-21 21:12:21
合計ジャッジ時間 2,421 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll th;
    cin >> th;
    string s(25, '9');
    auto f = [&](string s){
        int n = s.size();
        ll dp[n + 1][2][2][3] = {};
        dp[0][1][1][0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                int r = j & 1 ? s[i] - '0' : 9;
                for(int k = 0; k < 2; k++){
                    for(int l = 0; l < 3; l++){
                        if(i != n - 1){
                            if(k) dp[i + 1][(r == 0) & j][1][l] += dp[i][j][k][l];
                            if(3 <= r) dp[i + 1][(r == 3) & j][0][l] += dp[i][j][k][l];
                        }
                        if(5 <= r) dp[i + 1][(r == 5) & j][0][(l + 2) % 3] += dp[i][j][k][l];
                    }
                }
            }
        }
        return dp[n][1][0][0] + dp[n][0][0][0];
    };
    for(int i = 0; i < 25; i++){
        int ng = -1, ok = 9, mid;
        while(ng + 1 < ok){
            mid = (ng + ok) / 2;
            s[i] = mid + '0';
            if(th <= f(s)) ok = mid;
            else ng = mid;
        }
        s[i] = ok + '0';
    }
    reverse(s.begin(), s.end());
    while(s.back() == '0')s.pop_back();
    reverse(s.begin(), s.end());
    cout << s << '\n';
}
0