結果

問題 No.294 SuperFizzBuzz
ユーザー pekempeypekempey
提出日時 2015-10-23 23:44:41
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
6,816 KB
testcase_01 AC 6 ms
6,944 KB
testcase_02 AC 7 ms
6,940 KB
testcase_03 AC 6 ms
6,940 KB
testcase_04 AC 6 ms
6,940 KB
testcase_05 AC 6 ms
6,944 KB
testcase_06 AC 6 ms
6,944 KB
testcase_07 AC 7 ms
6,940 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 7 ms
6,940 KB
testcase_11 AC 7 ms
6,940 KB
testcase_12 AC 6 ms
6,944 KB
testcase_13 AC 7 ms
6,944 KB
testcase_14 AC 7 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0