051 Pascal

[•Florian]

Mda..eu iau 30 de puncte folosind relatia de recurenta...cu TLE pe restu`....se pare k tot la aia oficiala am ajuns...

[•Cristinatrifan]

Mai am acum o singura problema am implementat problema si am luat 90 de punce cu TLE la ultimul test, ma poate ajuta cineva?
Test Timp executie Memorie folosita Mesaj Punctaj/test
1  0ms        16kb         Ok!                      10
2  1052ms    39172kb   Ok!                      10
3  860ms     19640kb    Ok!                      10
4  704ms     26156kb    Ok!                      10
5  216ms     13720kb    Ok!                      10
6  0ms        12kb         Ok!                      10
7  0ms        8kb           Ok!                      10
8  36ms      896kb        Ok!                      10
9  0ms        8kb           Ok!                      10
10 1264ms  39168kb      Time limit exceeded. 0
Punctaj total 90

[•Cristinatrifan]

Cel mai rapid(optim)..cum pot afla la ce putere apare 2 intr-un numar???

[•Dastas]

probabil testezi daca n % 2 == 0 si apoi faci n /= 2

incearca sa faci operatiile astea pe biti: if ( (n & 1) == 0 ) pt modulo si n = (n >> 1) pt impartire

cel putin la mine asta a fost problema...

[•Cristinatrifan]

M-am gandit sa fac un vector in care sa retin pt i=1 la r puterea la care apare 2 de ex in i!. Nu ma poate ajuta cineva sa fac cel mai optim(in free pascal)

[•Dastas]

da, faci normal, vezi de cate ori se imparte la 2 cu un while. atata doar ca in loc de impartire la 2 si modulo 2, faci operatiile pe biti pe care ti le-am spus.

64 & 1 == 0, 64 >> 1 = 32 etc..

[•devilkind]

in pascal operatiile pe biti sunt :

& - AND
>> - shr

[•Cristinatrifan]

stai mai usor ca nu inteleg ce modulo? si cum se face impartirea pe biti?

[•devilkind]

pai zici ca ai nevoie sa vezi la ce putere apare 2 in descompunerea numarului x. Ei probabil ca u faci ceva de genu

Cod:

p:=0;
while (x mod 2 = 0) do begin x = x div 2;p:=p+1;end;

La sfarsit in variabila p ai exponentul. Ei operatori mod si div sunt destul de inceti. Avand in vedere ca ai impartire la 2 poti folosi operatii pe biti astfel:
ca sa afli restul lui x la 2 trebuie sa stii cel mai nesemnificativ bit din descompunerea lui (daca e 1 atunci restul e 1, altfel e 0). Spre ex 5 in baza 2 = 101 - ultimul bit e 1 deci restul e 1, 4 in baza 2 = 100 ultimul bit e 0 deci restul e 0. Ca sa afli acest bit poti sa aplici operatorul AND. Astfel: x AND 1 iti va returna 1 daca ultimul bit e 1, 0 in caz contrar, adica intocmai restul care iti trebuie tie.
Ptr impartire la 2 trebuie sa faci un shift right (shr) la tot sirul de biti. Spre exemplu 6 = 110. Daca mut toti biti o pozitie spre dreapta voi ajunge la 11 care e 3 (adik exact 6 div 2). Sintaxa ptr asta e :

Cod:

x := x shr k;

k e numarul de pozitii cu care muti sirul. Practic aceasta operatie il imparte pe x la 2^k, in cazul tau k trebuie sa fie 1.

DISCLAIMER: nu am mai scris sintaxa pascal de 2 ani asa ca nu sunt raspunzator ptr nici o greseala de sintaxa din acest post

[later edit] A treia observatie ar trebui putin editata ptr ca felul in care e scrisa akuma se intelege ca 0 e diferit de 1 (lucru care e destul de evident) si nu ca 0 factorial e 1.

[•Cristinatrifan]

Da asa faceam. Dar pt a descompune un numar in puteri de-ale lui 3 cum mai fac? ca banuiesc ca nu mai e buna ideea care ai spus-o

[•Cristinatrifan]

deci eu am facut asa:             
while p mod k=0 do
begin
        inc(nrdiv);
        p:=p div k;
end;

dar pt k=3 nu mai merge chestia cu biti nu?

[•devilkind]

nu nu mai merge.

[•Cristinatrifan]

Am facut pt 2 asa cum mi-ai spus:
while j AND 1=0 do
begin
       inc(nrdiv);
       j:=j shr 2;
end;
si mi se blocheaza programul. ce nu e bin3?

[•peanutz]

Vezi ca trebuie sa faci shr un singur bit, nu doi. Vezi ca scrie mai sus ce face fiecare. Baga-te cu watch, poate nu e de la secventa aia.

[•Cristinatrifan]

Multumesc Homorodean pt observatie si tie Devilkind!
Acum am luat 100!

[•Florian]

Eu am ceva de genu` asta:

Cod:

while(x&1==0)
		{
		jj++;
		x=x>>1;
		}

Nu mi se executa niciodata, iar x-ul sigur e par...in watch x&1 imi apare 0, insa nu se executa... Oare ce o avea?

{Edit later} M-am uitat mai sus pe forum si mi-am dat seama k nu folosisem paranteze...

[•taloibogdan]

De ce nu pot sa vad "imaginile" din solutia oficiala? Are ceva calculatorul meu sau e un bug?
Ce scrie in imaginile alea?

[•pauldb]

Nu e de la tine. Probabil acele imagini s-au pierdut cand a fost mutat site-ul.

[•Tedi]

nu inteleg de ce primesc la unele teste Killed by signal 8(SIGFPE).

pentru calculare linie folosesc formula data
a=fact(n)/(fact(n-j)*fact(j));

pentru factorial folosesc
for(int b=1; b<=n; b++)
            sum=sum*b;

am inteles ca eroare este data de o impartire la 0 sau la un overflow? cum sa dea overflow cand prima formula este indicata in enunt si trebuie folosita, iar factorialul este factorial... nu stiu un alt mod de a il calcula.

variabilele sunt de tip long. care sa fie buba?