Given an integer $x$, write a list of $\textbf{non-repeating positive integers}$ such that their sum is $x$, and whose length is maximum.
The input is made up of one integer $x$, $(1 \leq x \leq 10^{12})$.
Print a single integer l, the length of the answer, then the list on the next line.
If there are multiple answers you can print any.
| Input | Output |
|---|---|
1 Copy
|
1 1 Copy
|
3 Copy
|
2 1 2 Copy
|
6 Copy
|
3 1 2 3 Copy
|
The main idea of the solution is to find the largest $n$, such that $\frac{n*(n + 1)}{2} \leq x$, then adding $ x \mod \frac{n*(n + 1)}{2}$ to the last number in the list.
#include <bits/stdc++.h>
using namespace std;
long long x;
vector<int>v;
int main(){
scanf("%lld",&x);
int i = 1;
while(i <= x){
v.push_back(i);
x-=i;
i++;
}
if(x)v[v.size() - 1]+=x;
printf("%d\n",v.size());
for(auto i : v)printf("%d ",i);
puts("");
}