147 Ben

[•domino]

Aici puteţi discuta despre problema Ben.

[•Coty]

pentru a gasi nr de sol e nevoie de nr mari??? ca pe 2 teste imi da bine si al doilea numar, dar pe restu nu...

[•fireatmyself]

Numarul S va fi afisat modulo 32173.

S e numarul de variante. Deci nu ai nevoie de numere mari.

[•Coty]

ah, e a doua oara cand nu citesc asta... nici in concurs nu am fost atent da oricum at nu gasisem o formula valida...

Mersi mult!

[•MciprianM]

Se poate ca 2 masini sa soseasca in acelasi timp la benzinarie?
ex.:
3
1 5
1 6
2 8
L.E. Da.

[•vladiana]

cum se poate afla numarul de modalitati? megre cu dinamica? ca nu imi dau seama........numarul de statii merge cu greedy...da la nr de modalitati nu imi dau seama...need some help

[•DraStiK]

o idee cum poti gasi numarul de modalitati?

numarul de pompe se poate gasi si cu smenul lui Mars

[•raica_cristi]

multumes pentru idee dragos....inca nu stiu smenul lui mars dar il voi invata

[•bestalex]

cum pot afla testele puse de ei ? nu-mi pot da seama dc imi da wrong answar

[•Pepelea_Flaviu]

Nu le poti afla!

[•bogdan2412]

Testele de la această problemă conţineau caractere invalide la sfârşitul testelor. Problema a fost reevaluată, însă nu ar trebui să se schimbe niciun scor.

[•VisuianMihai]

Imi poate spune si mie cineva cum pot afla numarul de combinari la benzinarie?

[•MacWonk]

SPOILER ALERT!

Cum am reusit sa calculez numarul de modalitati:

In primul rand cand citim intervalele vom retine care este valoarea maxima dintre capetele din dreapta ale intervalelor si de asemenea vom retine pentru fiecare capat stanga cate intervale pornesc din acesta, adica cate masini vor intra in benzinarie in momentul CapatStangaInterval.

Calculam intr-un vector A numarul de masini aflate in benzinarie la un anumit moment i (i>=1 , i<=MaxDreaptaInterval) si astfel aflam si care este numarul de pompe necesare (pompe).

Initializam numarul de modalitati cu 1 (rez=1) si mergem cu un i (i>=1 , i<=MaxDreaptaInterval) calculand la fiecare pas rez*=aranjamente(pompe-(A[ i ]-CateIncepIn[ i ]),CateIncepIn[ i ]). Adica in fiecare moment vedem in cate moduri putem baga in benzinarie masinile care acum ar intra in ea, adica aranjamente de cate pompe libere avem luate cate masini intra in benzinarie in momentul respectiv.

[•luci2000]

Problema "ben" este data ca exemplu de problema rezolvabila cu AIB dar ea se rezolva mult mai usor fara AIB.

[•patcasrares]

Imi poate spune si mie cineva cum pot afla numarul de combinari la benzinarie?