infoarena

Aici puteţi discuta despre problema Pascal (http://infoarena.ro/problema/pascal).

:cry: Va rog mult.... am incercat exact metoda din solutiile de la pre ONI runda 2... Exact asa....
parcurg randul....calculez puterea fact. primi in desc. lui r! apoi in r-c! si apoi in c!. Apoi fac puterea lui r - puterea lui r-c - puterea lui c. Am tratat si cazul divizorilor neprimi. Si nu iau decat 60 de puncte. Oricine stie o idee de optimizare... Macar un indiciu....

Calculeaza intr-un vector puterea factorilor din numerele de la 1 la r ( fac = fac[i-1] + nrdiv(i) ) si dupa aia la verificare vezi dc fac[r] - fac[r-i] - fac > 0, i de la 1 pana la r
Daca calculai pt fiecare elem numarul de factori din r-c! si din c!, calculai de 2 ori numarul de factori pt fiecare numar de la 1 la r.
ex:
r=5 c=1 calculai fac(1) si fac(4)
r=5 c=4 calculai fac(4) (din nou) si fac(1) (din nou)

si eu tot 60 de puncte luam.. dar am facut urmatoarele optimizari:
1) mergi doar pana la r/2, nu verifici tot randul fiindca e simetric
2) calculezi puterea la care apare d in r! (fie ea "p"), si dupa aia ca sa vezi puterea la care apare in (r-1)! scazi din p puterea la care apare d in descompunerea lui r, dupa aia scazi din noua putere puterea la care apare d in r-1.. si tot asa.. acelasi idee o aplici si pentru a vedea puterea lui d in j!

succes.

Mersi amandurora.... Cu varianta cu vectorul am luat 100 de puncte \:D/ . Iar u-92 mi-a lamurit ideea mea originala.... Fiindca chiar nu intelegeam ( P.S. : Si eu mergeam tot pana la r/2  :wink: ) de ce nu mergea cu formula si acum e destul de clar. Multumesc mult! Bafta in continuare!  :wink:

40/100... iau WA la 6 teste.
am citit si articolul cu solutie, si am vazut ca trebuie facut cazul cand d nu este prim.

...nu merge sa se calculeze la fel ? adica [n/d] + [n/d^2] + [n/d^3] + ...

NU. Daca vrei sa afli puterea la care se afla 4 de ex. in 10! atunci ti-ar da:
[10/4]+[10/16]=2. Daca insa ai calcula puterea la care se afla 2 in 10 ! si ai imparti totul la 2 ( 4=2^2 ) ai obtine: ( [10/2] + [10/4] + [10/8] ) / 2 = ( 5 + 2 + 1 ) / 2 = 4. Formula care ai zis-o merge doar pentru numere prime. In cazul de mai sus, cand calculai cu [10/4]+[10/16]+.. se ignora un factor de 2 din numarul 2,  unul din numarul 6, unul din 8 si unul din 10. Inmultite acesti factori pierduti dau 2^4 = 4^2 de unde rezulta diferenta de 2 data de cele doua calcule.

da... good point.. mersi mult.

i'll never solve problems after 0:00 again :D

Imi spune cineva ce poate sa fie cu "Fisier de iesire lipsa!". Programul meu imi creeaza fiesierele si imi da raspunsuri corecte iar cand o trimit primesc aceeasi eroare si 0 pc.
 Please I'm desperate! :fighting:

Sigur ai scris corect numele fisierului de iesire ?

Zi-mi user-ul tau pe infoA.

Silviu

Acelasi, Crusher. Dar am facut-o inca o data de la inceput si acum imi da cat de cat un amarat de 10 pc. Dar ieri am descoperit o mica mare ghidusie si am sa incerc cu aia sa vad cum se descurca in lume ca e mai optima decat prima.   :shock:

mai ce inseamna SIGKILL am trimis acesta problema si mi-a dat SIGKILL la fiecare test :'(

Ai declarat mai mult de 64 MB, cred ...

cand depasesti dimensiunea tablourilor, pe care ai declarat-o, iti da erori de genul asta:
sigkill sau sigsegv

Bun...si pt a calcula n!/(n-p)!*p! solutia optima care ar fi? ca banuiesc ca nu backtracking

Nu prea vad ce treaba ar avea back-ul...Vezi poate te ajuta articolul cu solutii.... [ http://infoarena.ro/preoni-2005/runda-2/solutii ]

n!/((n-p)!*p!) - nu n!/(n-p)!*p!, adica combinari de n luate cate p. Exista o recurenta pentru asa ceva, si anume C(n, p) = C(n-1, p-1) + C(n-1, p).

Vezi triunghiul lui pascal.

1
1 1
1 2 1
1 3 3 1

C(n, 0) = C(n, n) = 1

Florian in caz ca nu te-ai prins trebuie sa generezi un vector in care sa retii toate numerele de pe al n rand al triunghiului pascal!! si spune ca se genereaza cu n!/(n-p)!*p!.......daca intelegi ce spun.....si homorodean chiar atat de proasta nu sunt ca sa nu stiu cum e...scuze am uitat o paranteza

Este bine...am implementat relatia de recurenta si imi iese, insa nu ar trebui C(0,0)=1 in loc de c(n,0)?


Am spus doar k nu are ce cauta back-ul...relatia pe care a dat-o Andrei Homorodean kred k este arhisuficienta...

Ms....pai da dar mi-ai dat sa ma uit peste solutia oficiala..dar acolo nu spune nimic despre asta :P
si nu ar trebui C(0,0) in loc fde C(n,0)--> pt ca n!/((n-0)!*0!)=1

Ok. Insa am zis "poate te ajuta"..! Un articol cu solutii iti poate oferi idei. Intr-adevar..se pare k nu zice nimik de ideea pe care ai abordat-o tu, insa eu am vrut doar sa ajut. :D Orikum..e bine k am invatat relatia de recurenta pt triunghiul lui Pascal... Multumesc, Andrei Homorodean!  :thumbup:

n ia valori de la 0 incepand.(n nu tine de datele problemei sau ceva in genul, vorbesc de generalitate)

 ](*,) Mda...greseala mea..Abia am invatat recursivitatea si ink o mai incurc..sorry..

Mai am folosit recurenta c(n,p)=c(n-1,p-1)+c(n-1,p), insa iau TLE la 8 test...ma poate ajuta cineva pls?

Incearca solutia oficiala, m-am uitat si eu peste sursa acum(o facusem mai demult), si am facut ca si in solutia oficiala. Cam multe TLE indeed :P

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

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

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

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

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)

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

in pascal operatiile pe biti sunt :

& - AND
>> - shr

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

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

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 :
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 :P

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

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

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?

nu nu mai merge.

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?

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.

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

Eu am ceva de genu` asta:


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

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

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

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

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?