Olimpiada Judeteană de Informatică
9 martie 2002, ora 9
00

CLASELE XI-XII

Problema 2 (Nunta)

Documentul Microsoft Word

În fata palatului Printesei Mofturoase se află N petitori asezati la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre pretioase pe care doreste să le ofere printesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, printesa a decis să-i determine ca N-1 dintre ei să renunte în chip pasnic, petitorul rămas devenind alesul printesei (indiferent de numărul de pietre pretioase detinute de acesta).

Doi petitori vecini la coadă se pot întelege între ei astfel: cel care are mai putine pietre pretioase 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 fată de câte avea. Dacă doi petitori au acelasi număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său.

Un petitor se poate întelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui petitor, toti cei din spatele lui avansează.

De exemplu: pentru configuratia alăturată de 5 petitori, un sir posibil de negocieri care conduc la reducerea cozii la un singur petitor este: se înteleg vecinii 4 cu 5 si pleacă 4, se înteleg apoi 1 cu 2 si plea1, se înteleg apoi 3 cu 2 si plea3, se înteleg 2 cu 5 si pleacă 5. Astfel petitorul 2 câstigă mâna prefrumoasei printese, oferindu-i 0 pietre pretioase ca dar de nuntă.

Fie P numarul de pietre pretioase pe care le are petitorul care va deveni alesul printesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

Fisierul de intrare nunta.in contine:
- pe prima linie num
ărul de petitori: n (1 £ n £ 50).
- pe a doua linie, n numere naturale din intervalul [0, 20], reprezentând num
ărul de pietre pretioase pe care le detin petitorii, în ordinea în care stau la coadă.

Fi
sierul de iesire nunta.out va contine:
- pe prima linie num
ărul m de valori distincte ce pot fi obtinute
- pe a doua linie cele m valori ordonate cresc
ător, reprezentând valorile care se pot obtine.

Exemplu:

nunta.in
4
1 4 2 6
nunta.out
3
1 3 5

Timp maxim de executare: 1 secundă / test

Închideti fereastra curentă pentru revenire