# PBinfo #4251 – numereOJI – Rezolvare C++

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

## Enunț

Gigel este un mare pasionat al cifrelor. Orice moment liber şi-l petrece jucându-se cu numere. Jucându-se astfel, într-o zi a scris pe hârtie 10 numere distincte de câte două cifre şi a observat că printre acestea există două submulţimi disjuncte de sumă egală. Desigur, Gigel a crezut că este o întâmplare şi a scris alte 10 numere distincte de câte două cifre şi spre surpriza lui, după un timp a găsit din nou două submulţimi disjuncte de sumă egală.

Cerința
Date 10 numere distincte de câte două cifre, determinaţi numărul de perechi de submulţimi disjuncte de sumă egală care se pot forma cu numere din cele date, precum şi una dintre aceste perechi pentru care suma numerelor din fiecare dintre cele două submulţimi este maximă.

Date de intrare
Fișierul de intrare numereoji.in conține pe prima linie 10 numere naturale distincte separate prin câte un spaţiu x1 x2 ... x10.

Date de ieșire
Fișierul de ieșire numereoji.out va conține trei linii. Pe prima linie se află numărul de perechi de submulţimi de sumă egală, precum şi suma maximă obţinută, separate printr-un spaţiu. Pe linia a doua se află elementele primei submulţimi, iar pe linia a treia se află elementele celei de a doua submulţimi, separate prin câte un spaţiu:


NrSol Smax, unde NrSol – numărul de perechi; Smax – suma maximă
x1 ... xk – elementele primei submulţimi
y1 ... yp -	elementele celei de a doua submulţimi

Restricții și precizări

10 ≤ xi, yi ≤ 99, pentru 1 ≤ i ≤ 10
1 ≤ k, p ≤ 9
Ordinea submulţimilor în perechi nu contează.
Perechea de submulţimi determinată nu este obligatoriu unică.

Exemplu:
numereoji.in

60 49 86 78 23 97 69 71 32 10
numereoji.out

65 276
78 97 69 32
60 49 86 71 10
Explicație
Sunt 65 de soluţii; suma maximă este 276, s-au folosit 9 din cele 10 numere; prima submulţime are 4 elemente, a doua are 5 elemente.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("numereoji.in");
ofstream fout("numereoji.out");
int a[12], t[12], n, cnt, sol[12], smax;
void Citire()
{
    n = 10;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
}
void Generare()
{
    int i, s1, s2, j;
    smax = 0;
    while (t[0] == 0)
    {
        /// next subm.
        for (i = n; i >= 1 && t[i] == 2; i--)
            t[i] = 0;
        t[i]++;
        /// calcul
        s1 = s2 = 0;
        for (i = 1; i <= n; i++)
            if (t[i] == 1) s1 += a[i];
            else if (t[i] == 2) s2 += a[i];
        if (s1 == s2 && s1 != 0)
        {
            cnt++;
            if (smax < s1)
            {
                smax = s1;
                for (j = 1; j <= n; j++)
                    sol[j] = t[j];
            }
        }
    }
    cnt /= 2;
    fout << cnt << " " << smax << "\n";
    for (i = 1; i <= n; i++)
        if (sol[i] == 1) fout << a[i] << " ";
    fout << "\n";
    for (i = 1; i <= n; i++)
        if (sol[i] == 2) fout << a[i] << " ";
    fout << "\n";
    fout.close();
}
int main()
{
    Citire();
    Generare();
    return 0;
}
```

## Resurse

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