Pracsiu Dan (dnprx) Fie şirul tuturor numerelor naturale de la 1 la un număr oarecare N. Considerând asociate câte un semn (+ sau -) fiecărui număr şi adunând toate aceste numere cu semn se obţine o sumă S. Problema constă în a determina pentru o sumă dată S numărul minim N pentru care, printr-o asociere de semne tuturor numerelor de la 1 la N, se poate obţine S.
Cerința
Pentru un S dat, găsiţi valoarea minimă N şi asocierea de semne numerelor de la 1 la N pentru a obţine S în condiţiile problemei.
Date de intrare
Fișierul de intrare sumaoni.in conține pe prima linie un întreg pozitiv S reprezentând suma ce trebuie obţinută.
Date de ieșire
Fișierul de ieșire sumaoni.out va conține pe prima linie numărul minim N pentru care se poate obţine suma S, iar pe următoarele linii, până la sfârşitul fişierului, numerele care au semn negativ, câte unul pe linie. Ordinea de afişare a numerelor nu are importanţă. Celelalte numere care nu apar în fişier se consideră pozitive.
Restricții și precizări
1 ≤ S ≤ 100.000- Dacă există mai multe soluţii se cere doar una.
Exemplul 1:
sumaoni.in
12
sumaoni.out
7 1 7
Explicație
Suma 12 se poate obţine din minimum 7 termeni astfel: 12 = -1 + 2 + 3 + 4 + 5 + 6 - 7. Atenţie: nu este singura posibilitate de asociere de semne termenilor de la 1 la 7.
Exemplul 2:
sumaoni.in
15
sumaoni.out
5
Explicație
Suma 15 se poate obţine din minimum 5 termeni astfel: 15 = 1 + 2 + 3 + 4 + 5. Pentru că toate numerele din șir au semnul +, atunci se afișează doar valoarea lui N.