889 Mins

[•pauldb]

Aici puteti discuta despre problema Mins.

Problema a fost adaugata de Vlad Gavrila. Mai multe detalii la Extinde arhiva.

[•wefgef]

Ar merge bagat si numarul problemei in titlul topicului .

[•Florian]

Am rezolvat problema de 70 de puncte. Am TLE. Vreau sa stiu daca e buna ideea. Folosesc acelasi lucru ca la problema "Frac" - principiul includerii si excluderii. Asadar, am ceva de genul:

   for(i = 1; i <= min; ++i)
      sol += phi ( i , max) ;

phi( i , max ) intoarce numarul de numere prime cu i si mai mici decat max. Initial, pentru toate numerele de la 1 la min calculez factorii primi si ii retin (folosind ciurul lui Erathostene). Avandu-i retinuti, aplic functia phi (exact ca la "frac"). Ceva idei de optimizare? [ in caz de aceasta este solutia buna ] Multumesc.

[•valentin.harsan]

nu trebuia sa fie c si d maxim 5000?
la lot asa era

[•eudanip]

Ba in mod normal da. Dar aici a fost pusa cu limita mai mare ca sa bage lumea in n*log(n). Inveti mai multe in felul acesta. Practic nu e chiar aceeasi problema ca la lot.

Bafta multa.

[•veleandu]

Dani daca nu sunt prea discret 
Eu am de gand sa iau toate numerele prime pana la min (c,d) si sa fac un pinex ..
adica ..
rez= c*d - (min(c,d)/primul numar prim ) - .. + (mind(c,d)/(primul numar prim*al doilea)) .. si tot asa : )

cred ca nu e optim 
dar nu vad alta solutie.
macar niste indicii de rezolvare va rog ? 

[•veleandu]

scuze  mergea prost netul de asta am postat de 2 ori nu stiam ca s-a postat prima data  si nu gasesc butonul de erase post 

[•eudanip]

Dani daca nu sunt prea discret 
Eu am de gand sa iau toate numerele prime pana la min (c,d) si sa fac un pinex ..
adica ..
rez= c*d - (min(c,d)/primul numar prim ) - .. + (mind(c,d)/(primul numar prim*al doilea)) .. si tot asa : )

cred ca nu e optim 
dar nu vad alta solutie.
macar niste indicii de rezolvare va rog ? 

Pai da asta nu e back ce zici tu?
Gandestete ce reprezinta dreptele alea si incearca sa te gandesti cum poti aplica ciurul.

Bafta multa.

[•vladdobro07]

aceasta problema...^woow

[•vladdobro07]

problema^astae de_poveste