986 Numar4

[•wefgef]

Aici puteti discuta despre problema Numar4.

[•vladtarniceru]

am facut-o  .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 

[•SpiderMan]

Nu mai da idei alta data .... 

[•andrei.finaru]

Am si eu o observatie: nu cumva la:

Date de ieşire: fişierul numar.out va conţine:

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)

[•wefgef]

Am modificat.

[•petro]

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

[•SpiderMan]

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.

[•andreea29]

q poate fi si fractie periodica?

[•Magnus]

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

[•TheNechiz]

Iua 95 p   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 ?

[•danalex97]

Probabil ca operatiile nu sunt optime.

Incearca la impartire ceva de genul:

Cod:

void div(int A[],int Size, int B)
{
      int i, t = 0;
      for (i = Size; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; Size > 1 && !A[ Size ]; Size--);
}

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

[•TheNechiz]

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 

[•danalex97]

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 )

[•TheNechiz]

Ce putem face ?

[•Steve]

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:

Cod:

int F (int v[])
{
    .........
}

[•danalex97]

10x. 

[•TheNechiz]

Mission Accomplished

[•beldeabogdan]

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

[•visanr]

X % 2 e echivalent cu X & 1.

[•ctlin04]

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