#55398 (C++11（廃止可能性あり）) No.294 SuperFizzBuzz

• 問題: No.294 SuperFizzBuzz
• ユーザー: pekempey
• 提出日時: 2015-10-23 23:44:41
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 7 ms / 5,000 ms
• コード長: 1,978 bytes
• コンパイル時間: 1,646 ms
• コンパイル使用メモリ: 164,304 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-09-13 03:41:10
• 合計ジャッジ時間: 2,435 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 12

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
const ll inf = 2e18;
ll dp[120][2][240]; // len, less, num 5
template<class T>
ostream &operator <<(ostream &os, const vector<T> &v) {
    rep (i, v.size()) {
        if (i) os << " ";
        os << v[i];
    }
    return os;
}
ll calc(ll a, int len) {
    memset(dp, 0, sizeof(dp));
    vector<int> v;
    rep (i, len) {
        v.push_back(a % 2);
        a /= 2;
    }
    int n = v.size();
    reverse(v.begin(), v.end());
    dp[0][0][0] = 1;
    rep (i, n) rep (j, 2) rep (k, 120) {
        int ub = 1;
        if (!j) ub = v[i];
        rep (x, ub + 1) {
            ll &next = dp[i + 1][j || x < ub][k + (x == 1)];
            next += dp[i][j][k];
            chmin(next, inf);
        }
    }
    ll ans = 0;
    rep (j, 2) rep (k, 1, 120) if (k % 3 == 2) {
        ans += dp[n][j][k];
        chmin(ans, inf);
    }
    return ans;
}
int len(ll a) {
    int res = 0;
    while (a) {
        res++;
        a /= 2;
    }
    return res;
}
string tostr(ll r, int len) {
    string s;
    rep (i, len) {
        if (r % 2 == 0) {
            s += "3";
        } else {
            s += "5";
        }
        r /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}
int main() {
    int n;
    cin >> n;
    ll l = 1, r = 18;
    vector<ll> sum(60);
    rep (i, 1, 60) {
        sum[i] = calc((1ll << i) - 1, i);
    }
    ll total = 0;
    int length = 0;
    rep (i, 1, 60) {
        if (total + sum[i] >= n) break;
        total += sum[i];
        length = i;
    }
    length++;
    l = 1, r = (1ll << length) - 1;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        ll ret = calc(m, length);
        if (ret + total >= n) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << tostr(r, length) + "5" << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX