051 Pascal

[•domino]

Aici puteţi discuta despre problema Pascal.

[•calinux]

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

[•bogdan2412]

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)

[u-92]

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.

[•calinux]

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

[cristi8]

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

[•bogdan2412]

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.

[cristi8]

da... good point.. mersi mult.

i'll never solve problems after 0:00 again

[•Crusher]

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!

[•silviug]

Sigur ai scris corect numele fisierului de iesire ?

Zi-mi user-ul tau pe infoA.

Silviu

[•Crusher]

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.  

[•razvan2006]

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

[•Marius]

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

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

[•points_hunter]

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

[•Cristinatrifan]

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

[•Florian]

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

[•peanutz]

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

[•Cristinatrifan]

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

[•Florian]

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

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

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

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

[•Cristinatrifan]

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

[•Florian]

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. Orikum..e bine k am invatat relatia de recurenta pt triunghiul lui Pascal... Multumesc, Andrei Homorodean! 

[•peanutz]

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

[•Florian]

  Mda...greseala mea..Abia am invatat recursivitatea si ink o mai incurc..sorry..

[•Cristinatrifan]

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?

[•peanutz]

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