Задача на поиск максимального количества различных слагаемых

Условия задачи

По данному числу 1≤n≤109 найдите максимальное число k, для которого n можно представить как сумму k различных натуральных слагаемых. Выведите в первой строке число k, во второй — k слагаемых.

Стоит отметить, что программа должна работать не более 5 сек. и использовать не более 256МБ ОЗУ.

Sample Input 1:

4

Sample Output 1:

2
1 3 

 

Sample Input 2:

6

Sample Output 2:

3
1 2 3

Для начала достаточно предположить, что максимальное количество слагаемых мы получим, складывая числа с минимальным значением. Также мы можем легко проверить тот факт, что:

сумма всех чисел от 0 до половины данного всегда больше или рано ему

Это все сильно облегчает нашу задачу, так как мы потратим минимум в 2 раза меньше времени, чем при переборе всех чисел от 0 до n. Также уйдет меньше памяти и времени за счет того, что будем работать с небольшими числами по сравнению с тем, что было бы, работая мы с числами >= (n+2)/2.

Собственно перейдем к решению задачи:

#include <iostream>
#include <vector>

using namespace std;

int main(){
    unsigned long int n; // на входе большое положительное число. Длины int может не хватить.
    cin >> n;
    unsigned int x = 0, i = 1, c_sum = n;
    vector<int> nums; // вектор, куда складываем все слагаемые. Можно было обойтись динамическим массивом. как мы, собственно, решили изначально задачу. Но с векторами удобнее и, как показалось, быстрее.

    while (c_sum > 0) {
        if (i < c_sum)
            /**
             * Ниже самое сладкое в данном алгоритме. Если следующая цифра будет больше остатка, то не следует добавлять ее в вектор.
             * Да и все остальные тоже, так как последняя цифра будет равняться остатку.
             */
            if (i+1 > c_sum-i)
                i = c_sum;
        nums.push_back(i);
        x++;
        c_sum -= i;
        i++;
    }

    cout << x << endl;
    for (vector<int>::iterator it = nums.begin();
         it != nums.end(); ++it){
        cout << *it;
        if ( it+1 != nums.end() )
            cout << ' ';

    }
    cout << endl;
}

Вот так примерно и решается данная задача.