Cerință
Micul Gates a mers la magazinul de bijuterii pentru a-și confecționa un mărțișor. El dispune de bile care dorește să fie așezate sub forma unui triunghi astfel încât oricare rând al triunghiului (începând cu ) să aibă exact bile, toate de aceeași valoare. Se cunoaște cât valorează fiecare dintre bilele pe care el le are și dorește ca mărțișorul să mai îndeplinească următoarea condiție: valoarea oricărei bile să fie egală cu suma valorilor celor două aflate sub ea.
Să se determine dacă se poate realiza un mărțișor folosind toate bilele date. În acest caz vom afișa valorile sale, în ordinea din triunghi, de sus în jos. În caz contrar vom afișa suma valorilor bilelor de pe un mărțișor care se poate forma cu o parte dintre ele și care are această sumă a valorilor (notată de noi mai departe ) maximă.
Date de intrare
Fișierul martisor.in conține pe prima linie un număr . Pe linia a 2-a sunt numere separate prin spațiu, reprezentând valorile bilelor.
Date de ieșire
Fișierul martisor.out conține rezultatul astfel: dacă se poate forma un mărțișor cu toate valorile date, fișierul va conține pe linia componența liniei a triunghiului (numere separate prin spațiu). În cazul celălalt, în fișierul de ieșire se va scrie un singur număr, .
Restricții și precizări
- ;
- Valorile numerelor sunt cuprinse între și , inclusiv.
- Pentru de puncte, ;
- Un mărțișor trebuie să fie format din puțin două linii. Se garantează că datele de intrare asigură realizarea unui astfel de mărțișor.
Exemplul 1
martisor.in
6
3 6 3 12 6 3
martisor.out
12
6 6
3 3 3
Explicație
Noi ne imaginăm numerele așezate unul sub altul astfel:
12
6 6
3 3 3
Exemplul 2
martisor.in
14
1 1 1 2 2 4 4 3 3 6 6 6 1 18
martisor.out
12
Explicație
Nu se poate forma un mărțișor cu toate numerele. Se pot forma mai multe cu o parte dintre numere. Unele dintre ele sunt:
2
1 1
sau
4
2 2
1 1 1
sau
6
3 3
Ultima soluție care se poate vedea mai sus, are suma maximă, .