Fişierul intrare/ieşire:caraibe.in, caraibe.outSursăLot 2004
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Caraibe

Cei N pirati de pe Perla Neagra au facut recent o captura foarte importanta: un cufar cu 10.000.000.000 (zece miliarde) de banuti. Acum piratii au de rezolvat o problema si mai dificila: cum sa imparta banii.
Pentru impartire, piratii se aseaza in linie. Primul pirat va propune o schema de impartire a banilor. Daca un anumit numar de pirati nu sunt de acord cu aceasta schema, piratul va fi aruncat peste bord, si apoi urmatorul pirat va propune o schema de impartire, si tot asa. Piratii sunt foarte inteligenti: un pirat este de acord cu o schema de impartire doar daca aceasta ii aduce un avantaj strict (cel putin un banut) fata de ce ar obtine votand impotriva schemei. Pentru ca actioneaza numai pe baze rationale, piratii sunt si foarte predictibili. Cu alte cuvinte, un pirat poate anticipa decizia altor pirati pentru a lua o decizie proprie (aceasta inseamna si ca daca un pirat are mai multe posibilitati de a alege o schema de impartire, ceilalti pirati stiu ce varianta ar alege).
Depinzand de caracteristicile fiecarui pirat (forta, popularitate), numarul de pirati care trebuie sa fie de acord cu schema lui pentru a nu fi aruncat peste bord variaza. Sa zicem ca pentru piratul i (1 ≤ i < N) acest numar este Ai. Daca piratul i propune o schema, stim ca toti piratii pana la i-1 au fost aruncati deja peste bord. In afara de piratul i, mai exista N-i pirati. Daca cel putin Ai dintre acestia sunt de acord cu schema piratului i, comoara va fi impartita dupa aceasta schema. Altfel, piratul i va fi aruncat peste bord, si piratul i+1 va propune o schema. Pentru orice i, avem 0 ≤ Ai < N-i. Datorita acestei conditii AN-1=0, iar AN nu este definit (pentru ca piratul N este ultimul).

Cerinta

Primul pirat din linie doreste sa propuna o schema de impartire a banilor astfel incat sa nu fie aruncat peste bord, si el sa primeasca cat mai multi banuti. Determinati suma maxima pe care o poate primi. Se garanteaza ca exista o schema pe care o poate propune primul pirat, astfel incat el sa nu fie aruncat peste bord.

Date de Intrare

Fisierul de intrare caraibe.in contine pe prima linie numarul N de pirati. Pe urmatoarele linii se gasesc valorile A1, A2, ..., AN-2, cate o valoare pe o linie. Asa cum se mentioneaza mai sus, AN-1 este intotdeauna zero, si nu apare in fisier.

Date de Iesire

Fisierul de iesire caraibe.out va contine numarul maxim de banuti pe care ii poate primi primul pirat.

Restrictii

  • 2 ≤ N ≤ 65 000
  • 0 ≤ Ai < N-i

Exemplu

caraibe.incaraibe.out
4
1
1
9999999999

Explicatii

Schema propusa de primul pirat este: 9999999999 de banuti pentru el insusi, 1 banut pentru al treilea pirat si 0 (zero) pentru ceilalti. Asta il face pe piratul al treilea sa fie de acord cu schema. El rationeaza astfel: "piratii 2 si 4 nu sunt de acord; daca si eu sunt impotriva, piratul 1 va fi aruncat peste bord (A1=1); apoi piratul 2 va propune schema: 9999999999 de banuti pentru el insusi, 1 banut pentru piratul 4 si nimic pentru mine; piratul 4 va fi de acord, deci schema va fi acceptata (A2=1); motivul pentru care piratul 4 va fi de acord este ca in cazul in care piratul 2 e aruncat peste bord, eu imi voi acorda toti banii mie si el nu primeste nimic (A3=0)"

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content