Olimpiada Judeteană de Informatică
9 martie 2002, ora 900
CLASELE XI-XII
Problema 2 (Nunta)
Î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 pleacă 1, se înteleg apoi 3 cu 2 si pleacă 3, 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 pre
tioase 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.Fi
sierul de intrare nunta.in contine:Timp maxim de executare: 1 secund
ă / testÎnchide
ti fereastra curentă pentru revenire