==Include(page="template/taskheader" task_id="caraibe")==
==Include(page="template/raw")==
Link: [1]File-List
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 A[i]. 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 A[i] 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<=A[i]<N-i. Datorita acestei conditii A[N-1]=0, iar A[N] nu este definit (pentru ca piratul N este ultimul).
h2. 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.
h2. Date de Intrare
Fisierul de intrare caraibe.in contine pe prima linie numarul N de pirati. Pe urmatoarele linii se gasesc valorile A[1], A[2], ..., A[N-2], cate o valoare pe o linie. Asa cum se mentioneaza mai sus, A[N-1] este intotdeauna zero, si nu apare in fisier.
h2. Date de Iesire
Fisierul de iesire caraibe.out va contine numarul maxim de banuti pe care ii poate primi primul pirat.
h2. Restrictii
. 2 <= N <= 65 000
. 0 <= A[i] < N-i
h2. Exemplu
caraibe.in caraibe.out Explicatie
4 9999999999 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 (A[1]=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 (A[2]=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 (A[3]=0)".
1
1
==Include(page="template/taskheader" task_id="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 {$A{~i~}$}. 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 $A{~i~}$ 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 ≤ A{~i~} < N-i$}. Datorita acestei conditii {$A{~N-1~}=0$}, iar $A{~N~}$ nu este definit (pentru ca piratul $N$ este ultimul).
h2. 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.
h2. Date de Intrare
Fisierul de intrare $caraibe.in$ contine pe prima linie numarul $N$ de pirati. Pe urmatoarele linii se gasesc valorile {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N-2~}$}, cate o valoare pe o linie. Asa cum se mentioneaza mai sus, $A{~N-1~}$ este intotdeauna zero, si nu apare in fisier.
h2. Date de Iesire
Fisierul de iesire $caraibe.out$ va contine numarul maxim de banuti pe care ii poate primi primul pirat.
h2. Restrictii
* $2 ≤ N ≤ 65 000$
* $0 ≤ A{~i~} < N-i$
h2. Exemplu
table(example). |_. caraibe.in |_. caraibe.out |
| 4
1
1
| 9999999999 |
h3. 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 ({*A{~1~}=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 ({*A{~2~}=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 ({*A{~3~}=0*})"
==Include(page="template/taskfooter" task_id="caraibe")==
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/caraibe/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="caraibe")==
