# PBinfo #4245 – sumaONI – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("sumaoni.in");
ofstream fout("sumaoni.out");
void Sol(int n, int i)
{
    fout << n << "\n";
    if (i > 0)
    {
        while (i > 0)
            if (i <= n)
            {
                fout << i << "\n";
                i = 0;
            }
            else
            {
                fout << n << "\n";
                i -= n;
                n--;
            }
    }
}
int main()
{
    int s, n, d;
    fin >> s;
    n = (sqrt(1 + 8 * s) - 1) / 2;
    if ((n * (n + 1)) / 2 < s)
        n++;
    d = (n * (n + 1)) / 2 - s;
    if (d % 2 == 0) Sol(n, d / 2);
    else
    {
        n++;
        d = (n * (n + 1)) / 2 - s;
        if (d % 2 == 0) Sol(n, d / 2);
        else
        {
            n++;
            d = (n * (n + 1)) / 2 - s;
            Sol(n, d / 2);
        }
    }
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4245)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4245/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4245/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)