結果

問題 No.294 SuperFizzBuzz
ユーザー masamasa
提出日時 2015-10-23 23:48:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,308 ms / 5,000 ms
コード長 1,215 bytes
コンパイル時間 805 ms
コンパイル使用メモリ 72,456 KB
実行使用メモリ 440,284 KB
最終ジャッジ日時 2024-09-13 03:59:15
合計ジャッジ時間 16,419 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2,308 ms
439,976 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 117 ms
30,532 KB
testcase_09 AC 1,088 ms
221,704 KB
testcase_10 AC 2,288 ms
440,072 KB
testcase_11 AC 2,291 ms
440,040 KB
testcase_12 AC 2,285 ms
440,284 KB
testcase_13 AC 2,282 ms
440,048 KB
testcase_14 AC 2,288 ms
440,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

const int LIMIT = 30;

long long combination(long long a, long long b) {
	b = min(b, a - b);

	long long ret = 1;
	for (long long i = 1; i <= b; i++) {
		ret = ret * (a - i + 1) / i;
	}
	return ret;
}

int main() {
	int n;

	cin >> n;
	vector<long long> cnt(LIMIT, 0);

	for (int i = 3; i < LIMIT; i++) {
		for (int j = 2; j < i; j += 3) {
			cnt[i] += combination(i - 1, j);
		}
	}

	int order = 0;
	int sum = 0;
	for (int i = 0; i < LIMIT; i++) {
		sum += cnt[i];

		if (sum >= n) {
			order = i;
			sum -= cnt[i];
			break;
		}
	}

	// cout << order << endl;
	// cout << sum << endl;
	// cout << n - sum << endl;

	vector<string> nums(cnt[order], "");
	int idx = 0;

	for (int n5 = 2; n5 < order; n5 += 3) {
		string numstr(order - 1, '3');
		for (int i = 0; i < n5; i++) {
			numstr[numstr.size() - 1 - i] = '5';
		}

		do {
			// cout << numstr << endl;
			// nums.emplace_back(numstr);
			nums[idx] = numstr;
			idx++;
		} while (next_permutation(numstr.begin(), numstr.end()));
	}

	sort(nums.begin(), nums.end());
	cout << nums[n - sum - 1] << '5' << endl;
	return 0;
}
0