CODE FESTIVAL 2016 Final B - Exactly N points (緑色, 300 点)

1, 2, ..., i のうちのいくつか選んで和を取った値は、連続した自然数を作れる

• 問題へのリンク

問題概要

からいくつか選んでできる総和が となるようにしたい。

選んだ数の最大値が最小となるような場合の数を求めよ。

制約

• 

考えたこと

一般に、 によって作れる整数は の範囲をくまなく作れる。よって次のような解法が生える。

---

rem = N とする i = N, N-1, ..., 1 に対して

• rem > i * (i-1)/2 のとき、i を採用
• そうでなければ採用しなくてよい

---

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long rem = N;
    for (long long i = N; i >= 1; --i) {
        if (rem > i * (i-1) / 2) {
            cout << i << endl;
            rem -= i;
        }
    }
}