Fişierul intrare/ieşire:	numere8.in, numere8.out	Sursă	OJI 2003, clasa a 9-a
Autor	Marinel Serban	Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.1 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Numere8

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 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 numere8.in conţine pe prima linie 10 numere naturale distincte separate prin câte un spaţiu x₁ x₂ ... x₁₀

Date de ieşire

În fişierul de ieşire numere8.out veţi afişa 3 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ă)
x₁ ... x_k (elementele primei submulţimi)
y₁ ... y_p (elementele celei de a doua submulţimi)

Restricţii

• 10 ≤ x_i,y_i ≤ 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

Explicaţie

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.

Cum se trimit solutii?