195 Caraibe

[•danielp]

Aici puteţi discuta despre problema Caraibe.

[ag3nt_junior]

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.

[•devilkind]

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.

[ag3nt_junior]

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?

[u-92]

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

[•scipianus]

(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.