007 Datorii

[•Matrix]

hey  cosmin,  ce  ID de yahoo  messenger ai ?

[•Cosmin]

Ai glumit cred cu faza cu pascalu .... si eu tot in pascal lucrez de obicei.

[•Twister]

Ai glumit cred cu faza cu pascalu .....

     

[•Cosmin]

Bah Matrix, am vazut ca esti din Bistrita si am zis ca nu mai fac misto de tine, da can zici hey ma exasperezi vorbeste si tu ca omu normal ... id pe messenger iti zice bindea sau tucu

[•Matrix]

bine, scuze ca te-am enervat,    am  cerut id, pt ca si eu is din bistrita

[•Matrix]

acum si  Calin, si domnul profesor  sunt la Galati  si de aceea  te-am intrebat

[•Cosmin]

Forumu asta are optiune de a trimite mesaje private ... iti trimit acuma.

[•pirosl]

0.2....limita de timp? Cu tot cu arbori indexati binar si operatii la nivel de bit nu reusesc sa scot un timp mai bun de 0.21-0.23.

[•Cosmin]

Cum gasesti cel mai putin semnificativ bit diferit de 0?

[•pirosl]

Cum gasesti cel mai putin semnificativ bit diferit de 0?

Adun si scad cu formulele acestea (ma refer la noua pozitie in vector)
poz += (poz ^ (poz-1))&poz;
poz -= (poz^(poz-1))&poz;

[•Cosmin]

Probabil ai bushit altceva pe acolo, s-ar putea si sa ai un ciclu infinit pe undeva pt ca la depasire de timp evaluatoru iti opreste solutia.

[•pirosl]

Probabil ai bushit altceva pe acolo, s-ar putea si sa ai un ciclu infinit pe undeva pt ca la depasire de timp evaluatoru iti opreste solutia.

OK. Am gasit care era problema. Scrierea/citirea din fisier. Am schimbat de la c++ io la c io adica de la ifstream/ofstream la fscanf/fprintf....si intra lejer in timp. Foarte urat din partea lui

[•ldoc]

imi poate da shi mie cineva un test ca mie imi merg toate acasa shi iau tot 0 puncte

[•wickedman]

Ideea e să foloseşti un algoritm suficient de rapid, nu doar corect.
Probabil iei 0 puncte din cauză că obţii

Time Limit Exceeded

(btw, asta poţi vedea în monitorul de evaluare)

[•ldoc]

Prima data ma luat WA dar acum am rezolvat problema si iau TLE.
Imi spune si mie cineva echivalentul pascal la
poz += (poz ^ (poz-1))&poz;
poz -= (poz^(poz-1))&poz;

[•vladcyb1]

poz:=poz + ((poz)xor(poz-1))and(poz)
poz:=poz-((poz)xor(poz-1))and(poz)

[•LucAnd]

NU se poate asa ceva , am facut problema , am invata arbori indexati binari, am mers de la c++ la c ca sa-mi intre in timp si acuma aflu ca nu e bun rezultatu , exemplus si orice alt ceva am testat imi merge perfect , va rog da-ti-mi si mieva rog  un test mai complicat sa ma conving ca nu merge

nu mai conteaza , am reusit sa o fac , era o greseala stupida , ceva ce nu se observa decat la testele mari

[•devilkind]

am shi eu o nelamurire. De ce atunci cand folosesc urmatoarea functie ptr a determina nr de 0-uri terminale imi zice Run Error - invalid memory reference

Cod:

void nr0(int k)
{return (k^(k&(k-1)))>> 1;}

iar dak o folosesc pe urmatoarea

Cod:

int nr0(int k)
{int nr,x;
x=k;
nr=0;
while (!(x%2))
{x=x >> 1;nr++;}
return nr;
}

imi iesa din timp. Care e problema la prima functie??

[•silviug]

Pentru K = 10100 prima functie face asa:

(10100 ^ (10100 & 10011)) >> 1
(10100 ^ 10011) >> 1
(00111) >> 1
= 00011 = adica 3 in baza 10

=> Functia nu returneaza numarul de zerouri terminale !

Functia ta incearca sa determine cel mai nesemnificativ bit dar ar merge doar daca elimini siftarea la dreapta si ai inversa & cu ^ (cred). Daca faci lucru asta atunci functia va return 2^x, unde x e numarul de zerouri terminale (adica ce returneaza functia a doua).

Inainte sa folosesti o functie in programele tale, gandeste-te un pic ce face. Eventual ia un exemplu si vezi cum functioneaza. Eu cred ca ai incercat sa iei functia de-a gata de pe undeva si sa o bagi in programul tau (zic si eu, poate gresesc).

Silviu

[Later edit]: Btw tipul din avatarul tau e kinda` gay Sau e tipa ?

[•devilkind]

intr-adevar formula aia am gasit-o undeva insa am gasit-o asha cum mi-ai zis u (fara shiftare)  si imi afiseaza 2^x , x fiind nr de zerouri in baza 2, shi dak ii pun acea shiftare imi da exact x (nu asha ar trebui). VEZI CA AI GRESHIT CAND AI CALCULAT 10100 & 10011, E 10000. Shi plus dak ar fi asta ar trebuie sa dea Wrong answer nu run error - memory reference failed.


BTW :tipu de la avatar e DANI FILTH, shi nu e gay, ptr cei care nu au auzit de el e solistul trupei CRADLE OF FILTH, cine nu a auzit de aceasta trupa sa caute nishte melodii ptr ca (virgula) canta mishto, asta dak va place black metalul sau gothikul

[•devilkind]

scuze ptr insistenta dar ma lamureshte shi pe mine cineva pana la urma??

[•filipb]

Nu fa functie de fiecare data ca sa afli nr. de 0-uri terminale, pentru ca nu trebuie sa incepi numaratoarea de fiecare data de la 0. Uite, de exemplu, iti dau functia de query ( suma numerelor de la 1 la X ) - poate te lamureste:

Cod:

int query(int X)
{ int p; // numarul de biti de 0 terminali;
   int S = 0;

   while (X > 0)
   {
          S += v[X]; // v este AIBul tau
          while ( ((1<<p)  & X) == 0) p++;
          X -= (1<<p);
          p++;
   }
  return S;

}

Update-ul fa-l tu similar

[•silviug]

intr-adevar formula aia am gasit-o undeva insa am gasit-o asha cum mi-ai zis u (fara shiftare)  si imi afiseaza 2^x , x fiind nr de zerouri in baza 2, shi dak ii pun acea shiftare imi da exact x (nu asha ar trebui). VEZI CA AI GRESHIT CAND AI CALCULAT 10100 & 10011, E 10000. Shi plus dak ar fi asta ar trebuie sa dea Wrong answer nu run error - memory reference failed.

Intr-adevar am gresit acolo My bad

Raspunsul lui Filip e la obiect, te lamureste de ce iei TLE si cum ai putea sa scapi de el.

(2^x) >> 1 = (2^x) div 2 != x (pentru multe cazuri)

Eu cred ca tu sa vrei implementezi AIB-uri si nu-ti trebuie numarul de zero-uri terminale ci 2^(numarul de zerouri terminale). Asadar functia initiala fara shiftare will do (si solutia propusa de Filip merge dar cred ca e mai inceata).

Have fun,

Silviu

PS: Stim Cradle .. dar nu ne place Join the good side man!
 

[•devilkind]

intr-adevar ai dreptate am nevoie de 2^x. doar ca eu copil idiot faceam numaru de zerouri terminale shi apoi faceam 2^x, fara sa imi dau seama ca il aveam deja calculat. me stupid.

PS: Gusturile muzicale nu se discuta

[andreit1]

Ai citit ce s-a discutat mai sus pe forum? 2^nr_zerouri il calculezi in timp constant? Citirea si afisarea poti sa o faci linistit cu fscanf si fprintf ca intra in timp.