#55379 (C++11) No.294 SuperFizzBuzz

• 問題: No.294 SuperFizzBuzz
• ユーザー: masa
• 提出日時: 2015-10-23 23:39:04
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2,591 ms / 5,000 ms
• コード長: 1,068 bytes
• コンパイル時間: 1,689 ms
• コンパイル使用メモリ: 72,088 KB
• 実行使用メモリ: 462,036 KB
• 最終ジャッジ日時: 2024-07-23 18:12:44
• 合計ジャッジ時間: 18,251 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,376 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2,591 ms; 462,032 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	123 ms; 27,860 KB
testcase_09	AC	1,124 ms; 199,888 KB
testcase_10	AC	2,549 ms; 462,020 KB
testcase_11	AC	2,539 ms; 462,036 KB
testcase_12	AC	2,573 ms; 461,912 KB
testcase_13	AC	2,500 ms; 461,940 KB
testcase_14	AC	2,590 ms; 462,028 KB

ソースコード

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

	vector<string> nums;

	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);
		} while (next_permutation(numstr.begin(), numstr.end()));
	}

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

	return 0;
}