infoarena

Aici puteţi discuta despre problema Caraibe (http://infoarena.ro/problema/caraibe).

Hmm.. faina problema. Am incercat printr-o logica simpla, dar mi-a iesit din timp. Am vrut sa platesc cu cate un banut a[1] pirati, astfel incat pentru fiecare din ei cea mai buna alegere sa fie acceptarea ofertei.
Nu e convenabil niciodata sa-l platesc pe piratul 2, pentru el fiind mai convenabil sa ma refuze, sa urmeze la rand, si sa faca o oferta mai buna in favoarea lui). Oricare altul ma va accepta, doar daca in caz de refuz, piratul 2 ar putea plati pe altii, el ramanand pe dinafara. Opresc algoritmul cand am a[1] pirati care sa-mi accepte oferta.

Cu alte cuvinte, algoritmul meu ar arata cam asa:

Piratul 1 cauta a[1] pirati care sa-i accepte oferta;
        fiecare pirat se gandeste:
                {
                            - daca urmez eu -> refuz oferta piratului 1; (imi pot face o oferta mai buna)
                            - altfel
                                    - daca piratul i+1 (care ar urma dupa piratul 1)                     poate alege alti a[i+1] pirati care sa-i accepte oferta-> accept oferta piratului 1; (in caz de refuz, risc sa nu primesc nimic)
                                    - altfel -> refuz oferta piratului 1;
                 }

E ceva gresit in rationamentul meu? Se poate mai simplu? Astept idei de la cei care au rezolvat-o.

dak am inteles bine rationamentul tau u ii platesti cu cate un banut pe piratii 3 si 4 (toti piratii in afara de 2) shi atunci piratului 1 ii raman 999 999 998. Cel putin asha am inteles eu din rationamentul, e posibil sa fi greshit eu.

Nu. Pentru exemplul dat, functioneaza, chiar si pentru altele mai complicate luate de mine. Piratul 1 nu va plati decat a[1] pirati (minimul de pirati care trebuie sa fie de acord pentru ca acesta sa nu fie aruncat peste bord). Deci nu are rost sa-i platesc si pe 3 si pe 4. Caut doar 1 care va fi de acord cu oferta. Il platesc pe 3, el va fi de acord cu mine, si eu imi pastrez 999999999  de banuti.
Sunt sigur ca m-as putea convinge si singur daca as avea la dispozitie un test mai complicat, cu solutia corespunzatoare. Ma ajuta cineva?

scrie acolo ca problema a fost data la lot 2004. arhiva respectiva o gasesti pe info.devnet.ro la sectiunea download

(Scuze ca intervin pe un subiect vechi)

Am rezolvat acum ceva zile problema de 100pct atat in arhiva de probleme,cat si pe lista lui wefgef,dar sus inca apare "Scorul tău   N/A" ca si cum n-as fi trimis nicio sursa la problema asta.  :-k