# PBinfo #4234 – potriviri – Rezolvare C++

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

## Enunț

Cerința
Se dau două numere naturale nenule N și S. Determinați numerele distincte x1, x2, .., xN aparținând mulțimii {1, 2, ..., N} astfel încât 1 * x1 + 2 * x2 + .. + N * xN = S.

Date de intrare
Fișierul de intrare potriviri.in conține pe prima linie două numere naturale nenule N și S, separate printr-un spațiu, reprezentând numărul de numere, respectiv suma ce trebuie obținută.

Date de ieșire
Fișierul de ieșire potriviri.out va conține pe prima linie N numere naturale nenule, separate prin câte un spațiu, reprezentând soluția problemei. Dacă nu există soluție, pe această linie se va scrie numărul 0.

Restricții și precizări

2 ≤ n ≤ 1000
1 ≤ S ≤ 1.000.000.000
Dacă există mai multe soluții, se va scrie una singură, oricare din ele.

Exemplu:
potriviri.in

4 26
potriviri.out

3 2 1 4
Explicație
1 * 3 + 2 * 2 + 3 * 1 + 4 * 4 = 26.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int v[1003], sm[1003], n, s;
ifstream fin("potriviri.in");
ofstream fout("potriviri.out");
int main()
{
    int i, j, sa, dif, smin;
    bool ok;
    fin >> n >> s;
    sa = 0;
    for (i = 1; i <= n; i++)
    {
        v[i] = i;
        sa = sa + i * i;
        sm[i] = sa;
    }
    if (s>sa)
    {
        fout << "0\n";
        fout.close();
        return 0;
    }
    smin = 0;
    for (i = 1; i <= n; i++)
        smin = smin + (n - i + 1) * i;
    if (s < smin)
    {
        fout << "0\n";
        fout.close();
        return 0;
    }
    if (s == smin)
    {
        for (i = 1; i <= n; i++)
            v[i] = i;
        sa = smin;
    }
    while (sa>s)
    {
        ok = false;
        for (i = n; i >= 2; i--)
        {
            for (j = i - 1; j >= 1; j--)
            {
                dif = (v[i] * i + v[j] * j) - (v[i] * j + v[j] * i);
                if (dif > 0 && sa - dif >= s)
                {
                    smin = v[i];
                    v[i] = v[j];
                    v[j] = smin;
                    sa = sa - dif;
                    ok = true;
                    break;
                }
            if (ok) break;
            }
        }
    }
    for (i = 1; i <= n; i++)
        fout << v[i] << " ";
    fout << "\n";
    fout.close();
    fin.close();
    return 0;
}
```

## Resurse

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