infoarena

Aici puteti discuta despre problema Numar4 (http://infoarena.ro/problema/numar4).

am facut-o  :D .ideea este simpla,avand in vedere ca nr de jos este format doar din 1 si 0(de fapt e sub forma 1*(10^n)),va trebui sa impartim doar la 2 si 5,deci vom folosi un algoritm de impartire pt numere mari  :D :winner1:

Nu mai da idei alta data ....  :eyebrow:

Am si eu o observatie: nu cumva la:
ar trebui "numar4.out"? Ca bietul elev roman care a fost la OJI si a retinut titlul de acolo se poate incurca.(am luat 0 pct la primul upload pe fisier de iesire lipsa)

Am modificat.

am citit solutia oficiala..de ce b-ul e format numai din 1 si 0? spre ex, q=4.23872679, a=1598, b=377. daca e numai 1 si 0, atunci ar fi a=423872679, b=100000000. diferenta e mai mare...

Fii atenta : daca ai sa zicem primul exemplu, noi vrem de fapt sa scriem acel numar sub forma de fractie, si sa-l simplificam pana nu se mai poate. Dupa cum ai invatat in gimnaziu la matematica transformarile , spre exemplu daca avem un numar rational 0,5 , el poate fi scris sub forma de fractie asa : 5 / 10 = 1 / 2 ; alte exemple : 0, (5) = 5/9 ; 0 , 1(5) = ( 15 - 1 ) / 90 = 14 / 90 = 7 / 45 . Noi avem in primul exemplu q = 0, 375, adica 375 / 1000. Daca o sa tot simplifici, o sa ajungi la 5 / 8. La al doilea exemplu avem q = 12,34567, adica 12 intregi si 34567 / 100000. Numaratorul o sa fie dupa introducerea intregilor in fractie : 12 * 100000 + 34567 = 1234567, si fractia q = 1234567 / 100000. Aceasta nu mai poate fi simplificata, deci acesta este rezultatul.

q poate fi si fractie periodica?:)

din cate am inteles eu, nu (nu se precizeaza cum citesti perioada). :D
oricum eu am rezolvat-o doar pentru fractii neperiodice

Iua 95 p   :shock: TLE pe testul 18.

Fac simplificări cu 10,5,2.Nu știu cum aș mai putea să optimizez programul.
Vă rog , ar putea cineva să mă ajute ?

Probabil ca operatiile nu sunt optime.

Incearca la impartire ceva de genul:

Vezi sa simplifici in ordinea 10 , 5 , 2 si la impartirea cu 10 doar sa tai 0-uri.
Daca nu e asta vezi sa nu faci acelasi lucru de mai multe ori si daca lucrezi cu stringuri nu uita ca operatii gen strlen(s) au complexitate O(N).

Am încercat să tai doar zero-urile ,dar tot 95 de puncte iau.
Ți - am trimis un PM cu sursa , dacă poți să-mi spui și mie ce e greșit.
Mulțumesc pentru ajutor  :ok:

Hmm... Nu cred ca problema este de la sursa ta , ci timpul a fost scazut prea mult. Cu sursa veche care lua 100 iau , la fel ca tine , 95p.
Sursa mea veche facea 120ms pe testul 18 , iau acum apare depasit , desi sursa e aceeasi.

Cred ca limita de timp a fost schimbata si nu s-a updatat in enunt. Totusi eu cred ca limita ar putea fi marita putin. ( la 0.2 / 0.175 ) :ok:

Ce putem face ? :?

Mi-am batut un pic capul, am scos toate apelurile de functii si am facut impartirile la 2 pe biti si a intrat. Incercati asa...

Ideea e ca pierzi destul de mult timp atunci cand ai o functie de genu:

10x.  :ok:

Mission Accomplished :thumbup:

O rezolvare standard ia pe testul 18 in jur de 210 milisecunde.
Cum se face impartirea la 2 pe biti?

X % 2 e echivalent cu X & 1.

Eu am facut doua proceduri aparte pentru impartirea la 5 si la 2 fara operatii pe biti si a mers destul de bine http://infoarena.ro/job_detail/827557
Am declarat procedurile cu inline si fara parametri locali: inline void imparte();
Hope it helps  :)