結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー tubo28
提出日時 2015-12-26 20:50:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 223 ms / 5,000 ms
コード長 1,930 bytes
コンパイル時間 628 ms
コンパイル使用メモリ 64,972 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 00:36:54
合計ジャッジ時間 2,282 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::string solve()’:
main.cpp:88:35: warning: ‘ans’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |         res = string() + "35"[ans >> i & 1] + res;
      |                               ~~~~^~~~

ソースコード

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);
}

int select(vector<int> &a, int k) {
    for (int l = 0, r = a.size() - 1; l <= r; ) {
        int p = a[(l + r) / 2];
        int i = l - 1, j = r + 1;
        while (1) {
            while (a[++i] < p);
            while (a[--j] > p);
            if (i >= j) break;
            swap(a[i], a[j]);
        }
        if (k == i - l) return a[i];
        else if (k < i - l) { r = i - 1; }
        else if (k > i - l) { k -= (i - l + 1); l = j + 1; }
    }
    return -99999999; // k < 0 || k >= n
}

string solve() {
    --n;
    ll acc = 0;
    int w = 1;
    while (1) {
        if (acc + count(w) <= n) {
            acc += count(w);
            w++;
        }
        else {
            break;
        }
    }
    int k = 0;
    ll ans;
    for (int S = 0; S < 1 << w; ++S) {
        if (S & 1 && pc(S) % 3 == 0) {
            if (k == n - acc) {
                ans = S;
                break;
            }
            k++;
        }
    }
    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