CODE FESTIVAL 2016 Final: B - Exactly N points
分からなくて焦ったのだが、なんとなく書いてみたら通った。
solution
上限を決め打ちして大きいものから貪欲に採用する。上限を二分探索すれば$O(\sqrt{N} \log{N})$だが、小さい方から順に試しても$O(N)$。
implementation
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
vector<int> func(int n, int k) {
vector<int> result;
for (; k >= 1 and n != 0; k = min(k-1, n)) {
if (n >= k) {
n -= k;
result.push_back(k);
}
}
if (n) result.clear();
return result;
}
int main() {
int n; cin >> n;
repeat (k,n+1) {
vector<int> xs = func(n, k);
if (not xs.empty()) {
for (int x : xs) cout << x << endl;
break;
}
}
return 0;
}