Fișierul intrare/ieșire | submult.in, submult.out | Sursă | OJI 2003 clasa a 9-a |
---|---|---|---|
Autor | Marinel Șerban | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Submult (clasa a 9-a)
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ță
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 dintre 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 submult.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 submult.out 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 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
- 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
submult.in | submult.out | Explicații |
---|---|---|
60 49 86 78 23 97 69 71 32 10 |
65 276 78 97 69 32 60 49 86 71 10 |
65 de soluții; suma maximă este 276, s-au folosit 9 dintre cele 10 numere prima submulțime are 4 elemente, a doua are 5 elemente. |