nunta

Time limit: 0.02s Memory limit: 16MB Input: nunta.in Output: nunta.out

În faţa palatului Prinţesei Mofturoase se află NN peţitori aşezaţi la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre preţioase pe care doreşte să le ofere prinţesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prinţesa a decis să-i determine ca N1N-1 dintre ei să renunţe în chip paşnic, peţitorul rămas devenind alesul prinţesei (indiferent de numărul de pietre preţioase deţinute de acesta).

Doi peţitori vecini la coadă se pot înţelege între ei astfel: cel care are mai puţine pietre preţioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre faţă de câte avea. Dacă doi peţitori au acelaşi număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său.

Un peţitor se poate înţelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui peţitor, toţi cei din spatele lui avansează.

De exemplu: pentru configuraţia alăturată de 55 peţitori, un şir posibil de negocieri care conduc la reducerea cozii la un singur peţitor este: se înţeleg vecinii 44 cu 55 şi pleacă 44, se înţeleg apoi 11 cu 22 şi pleacă 11, se înţeleg apoi 33 cu 22 şi pleacă 33, se înţeleg 22 cu 55 şi pleacă 55. Astfel peţitorul 22 câştigă mâna preafrumoasei prinţese, oferindu-i 00 pietre preţioase ca dar de nuntă.

Cerință

Fie PP numarul de pietre preţioase pe care le are peţitorul care va deveni alesul prinţesei. Se cer valorile distincte ale lui PP la care se poate ajunge prin toate succesiunile de negocieri posibile.

Date de intrare

Fişierul de intrare nunta.in conţine:

  • pe prima linie numărul de peţitori: nn (1n501 ≤ n ≤ 50).
  • pe a doua linie, nn numere naturale din intervalul [0,20][0, 20], reprezentând numărul de pietre preţioase pe care le deţin peţitorii, în ordinea în care stau la coadă.

Date de ieșire

Fişierul de ieşire nunta.out va conţine:

  • pe prima linie numărul mm de valori distincte ce pot fi obţinute
  • pe a doua linie cele mm valori ordonate crescător, reprezentând valorile care se pot obţine.

Exemplu

nunta.in

4 
1 4 2 6

nunta.out

3
1 3 5

Log in or sign up to be able to send submissions!