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