•domino
|
|
« : Februarie 24, 2005, 20:51:47 » |
|
Aici puteţi discuta despre problema Pascal.
|
|
|
Memorat
|
|
|
|
•calinux
Strain
Karma: 5
Deconectat
Mesaje: 42
|
|
« Răspunde #1 : Aprilie 21, 2005, 21:48:05 » |
|
: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....
|
|
|
Memorat
|
"And all that is now, And all that is gone, And all that's to come, And everything under the sun is in tune But the sun is eclipsed by the moon" The Dark Side of The Moon - Pink Floyd
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Aprilie 22, 2005, 09:28:36 » |
|
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)
|
|
|
Memorat
|
|
|
|
u-92
Vizitator
|
|
« Răspunde #3 : Aprilie 23, 2005, 11:38:53 » |
|
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.
|
|
|
Memorat
|
|
|
|
•calinux
Strain
Karma: 5
Deconectat
Mesaje: 42
|
|
« Răspunde #4 : Aprilie 25, 2005, 08:40:16 » |
|
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!
|
|
|
Memorat
|
"And all that is now, And all that is gone, And all that's to come, And everything under the sun is in tune But the sun is eclipsed by the moon" The Dark Side of The Moon - Pink Floyd
|
|
|
cristi8
Vizitator
|
|
« Răspunde #5 : Mai 02, 2005, 23:29:51 » |
|
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] + ...
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #6 : Mai 03, 2005, 07:10:15 » |
|
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.
|
|
|
Memorat
|
|
|
|
cristi8
Vizitator
|
|
« Răspunde #7 : Mai 03, 2005, 10:01:40 » |
|
da... good point.. mersi mult. i'll never solve problems after 0:00 again
|
|
|
Memorat
|
|
|
|
•Crusher
Strain
Karma: -2
Deconectat
Mesaje: 11
|
|
« Răspunde #8 : Februarie 17, 2006, 16:01:40 » |
|
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!
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #9 : Februarie 17, 2006, 17:10:38 » |
|
Sigur ai scris corect numele fisierului de iesire ?
Zi-mi user-ul tau pe infoA.
Silviu
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•Crusher
Strain
Karma: -2
Deconectat
Mesaje: 11
|
|
« Răspunde #10 : Februarie 20, 2006, 12:43:16 » |
|
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.
|
|
|
Memorat
|
|
|
|
•razvan2006
Strain
Karma: 0
Deconectat
Mesaje: 4
|
|
« Răspunde #11 : Noiembrie 16, 2006, 13:52:29 » |
|
mai ce inseamna SIGKILL am trimis acesta problema si mi-a dat SIGKILL la fiecare test
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #12 : Noiembrie 16, 2006, 14:24:34 » |
|
mai ce inseamna SIGKILL am trimis acesta problema si mi-a dat SIGKILL la fiecare test Ai declarat mai mult de 64 MB, cred ...
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•points_hunter
Strain
Karma: -7
Deconectat
Mesaje: 26
|
|
« Răspunde #13 : Noiembrie 16, 2006, 18:32:57 » |
|
cand depasesti dimensiunea tablourilor, pe care ai declarat-o, iti da erori de genul asta: sigkill sau sigsegv
|
|
|
Memorat
|
Intr-o lume plina de prostie si noobism Ceva mai increzator, putin mai oportunist Nihil sine DEO(Iubeste si vei fi iubit , Nu uita niciodata ca esti om)
|
|
|
•Cristinatrifan
Strain
Karma: -9
Deconectat
Mesaje: 15
|
|
« Răspunde #14 : Mai 04, 2007, 21:18:59 » |
|
Bun...si pt a calcula n!/(n-p)!*p! solutia optima care ar fi? ca banuiesc ca nu backtracking
|
|
|
Memorat
|
|
|
|
|
•peanutz
|
|
« Răspunde #16 : Mai 04, 2007, 21:39:35 » |
|
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
|
|
« Ultima modificare: Mai 04, 2007, 21:43:59 de către Andrei Homorodean »
|
Memorat
|
....staind....
|
|
|
•Cristinatrifan
Strain
Karma: -9
Deconectat
Mesaje: 15
|
|
« Răspunde #17 : Mai 04, 2007, 21:51:37 » |
|
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
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #18 : Mai 04, 2007, 22:07:46 » |
|
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...
|
|
|
Memorat
|
|
|
|
•Cristinatrifan
Strain
Karma: -9
Deconectat
Mesaje: 15
|
|
« Răspunde #19 : Mai 04, 2007, 22:10:08 » |
|
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
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #20 : Mai 04, 2007, 22:14:34 » |
|
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!
|
|
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #21 : Mai 04, 2007, 22:22:51 » |
|
n ia valori de la 0 incepand.(n nu tine de datele problemei sau ceva in genul, vorbesc de generalitate)
|
|
|
Memorat
|
....staind....
|
|
|
•Florian
|
|
« Răspunde #22 : Mai 04, 2007, 22:24:46 » |
|
Mda...greseala mea..Abia am invatat recursivitatea si ink o mai incurc..sorry..
|
|
|
Memorat
|
|
|
|
•Cristinatrifan
Strain
Karma: -9
Deconectat
Mesaje: 15
|
|
« Răspunde #23 : Mai 04, 2007, 22:36:13 » |
|
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?
|
|
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #24 : Mai 04, 2007, 22:42:23 » |
|
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
|
|
« Ultima modificare: Mai 05, 2007, 11:43:42 de către Andrei Homorodean »
|
Memorat
|
....staind....
|
|
|
|