結果

問題 No.294 SuperFizzBuzz
ユーザー tubo28
提出日時 2015-12-26 20:47:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 789 ms / 5,000 ms
コード長 1,411 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 67,968 KB
実行使用メモリ 36,924 KB
最終ジャッジ日時 2024-09-19 00:36:41
合計ジャッジ時間 6,181 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <string>
#include <cstring>

using namespace std;

using ll = long long;

/*
5で終わって各桁の和が３の倍数
5は2, 3は0
5が3の倍数個
*/

ll n;

ll nCr(int n, int r) {
    static bool done[50 + 1][50 / 2 + 2];
    static ll dp[50 + 1][50 / 2 + 2]; // 400MB
    if (n < 0 || r < 0 || n < r) return 0;
    if (r == 0) return 1;
    if (r > n - r) r = n - r;
    ll &res = dp[n][r];
    if (done[n][r]) return res;
    done[n][r] = true;
    return res = nCr(n - 1, r - 1) + nCr(n - 1, r);
}

ll count(ll w) {
    ll res = 0;
    for (int i = 2; i <= w - 1; i += 3) {
        res += nCr(w - 1, i);
    }
    return res;
}

int pc(int s) {
    if (s == 0) return 0;
    return s % 2 + pc(s / 2);
}

string solve() {
    --n;
    ll acc = 0;
    int w = 1;
    while (1) {
        if (acc + count(w) <= n) {
            acc += count(w);
            w++;
        }
        else {
            break;
        }
    }
    vector<int> cand;
    for (int S = 0; S < 1 << w; ++S) {
        if (S & 1 && pc(S) % 3 == 0) {
            cand.push_back(S);
        }
    }
    sort(cand.begin(), cand.end());
    ll ans = cand[n - acc];
    string res;
    for (int i = 0; i < w; i++) {
        res = string() + "35"[ans >> i & 1] + res;
    }
    return res;
}

int main() {
    while (cin >> n) cout << solve() << endl;
}
0