infoarena

Aici puteţi discuta despre problema Cifre (http://infoarena.ro/problema/cifre).

oameni buni, la 50% din teste imi da TLE  ](*,)... deci trebuie sa fie o metoda mai scurta.. imi puteti da vreo idee ceva? va rog frumos  :fighting:

incearca solutia oficiala:

http://info.devnet.ro/articole.php?page=art&art=54

Ce greu merge generatorul random de la voi. In 0.2 secunde am putut genera doar 500 000 numere.
Oricum traiasca randomu.

Iau doar 50 de puncte... ](*,)exista vreo formula???(desi mie foarte greu sa cred k da)...da ti mi si mie, va rog, un indiciu care sa ma konduca spre o solutie de 100 de puncte...va rog... :-s

http://infoarena.ro/preoni-2005/runda-3/solutii  vezi articolu asta :P

Iata o solutie draguta la problema cifre :
Folosim o functie cif(x)=numarul de cifre c ale numarului x.
Daca distanta intre a si b <10000 atunci scoatem numarul cazurilor favorabile analizand fiecare numar.
Daca nu impartim intervalul [a,b] in subintervale
I0=[ a , x*10000 ),
I1=[ x*10000 . (x+1)*10000 )
I2=[ (x+1)*10000 , (x+2)*10000 )
...
Iultim=[ y*10000 , b ]

Cu exceptia primului si ultimului interval unde calculam cazurile favorabile  analizand fiecare numar pe celelalte intervale putem calcula cazurile favorabile folosind cif(x/10000) si o metoda simpla de numarare asupra careia voi reveni daca cineva insista.

Obtinem astfel un algoritm de O(sqrt(B-A)).

Cât ar trebui să aștept până mi se verifică sursa? Adică am încărcat o rezolvare pe site la această problemă și nu mi-a apărut punctajul. Cât ar trebui să aștept deobicei până apare?

De obicei dureaza cateva zeci de secunde, dar de data asta evaluatorul se blocase putin. L-am restartat si ar trebui sa ajunga si la sursa ta cat de curand.

Furtul meu va ramane in istorie  =D&gt;