SRM678 Div1 Easy AlmostFibonacciKnapsack

2016/04/07 (Thu) SRM 構築

問題

a[1] = 2, a[2] = 3, a[i] = a[i-1] + a[i-2] - 1 で作られる数列がある．整数 x が与えられるので， 数列に現れる数だけの和でx が表現できるか判定してください．

方針

IDに_を含む人のツイートを貼るとHTMLが崩れる

実装

class AlmostFibonacciKnapsack {
public:
    vector<int> getIndices(ll x) {
        vector<ll> a = { 2,3 };
        while (a.back() <= x) {
            a.push_back(a.back() + a.rbegin()[1] - 1);
        }
        a.pop_back();
        vector<int> res;
        for (int i = a.size() - 1; i >= 0; i--) {
            if (x >= a[i] && x - a[i] != 1) {
                x -= a[i];
                res.push_back(i + 1);
            }
        }
        return res;
    }
};