Codeforces Round #139 (Div. 2) B : Well-known Numbers
問題概要
十分長い0の後に1がある。これから、直前k(<10^9)項の和を末尾に加える操作を繰り返す。できた数の部分和がs(<10^9)になるようなものを構成する問題。
解法
sを作るには貪欲でやってよい。まずsを越えるまで数を列挙し、後は大きいものから選べるだけ選んでいく。また、部分和が2以上でないといけない制約があるのでそのときは0を利用する。
acceptされたコード
#include <cstdio> #include <vector> #include <algorithm> #include <functional> using namespace std; typedef long long int64; const int64 INF = int64(1.05e16); int64 S, K; vector<int64> nums; void init() { scanf("%lld%lld", &S, &K); } void generate() { nums.push_back(0); nums.push_back(1); int64 acc = 1; for (;;) { nums.push_back(acc); acc += nums.back(); if (int(nums.size()) > K) { acc -= nums[int(nums.size()) - K - 1]; } if (nums.back() > INF) { break; } } } void solve() { generate(); reverse(nums.begin(), nums.end()); vector<int64> ans; for (;S;) { vector<int64>::iterator itr = lower_bound(nums.begin(), nums.end(), S, greater<int64>()); S -= *itr; ans.push_back(*itr); } if (int(ans.size()) == 1) { ans.push_back(0); } printf("%d\n", int(ans.size())); for (int i = 0; i < int(ans.size()); ++i) { printf("%lld%c", ans[i], i==int(ans.size())-1 ? '\n' : ' '); } } int main() { init(); solve(); return 0; }