Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Mugur  (Citit de 4265 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Iunie 06, 2009, 00:25:51 »

Aici se pot pune întrebări legate de problema Mugur a concursului CCEX 2009.

Timpul alocat întrebărilor este de 1 oră. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea îşi găseşte răspuns în enunţul problemei, răspunsul va fi FĂRĂ COMENTARII.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #1 : Iunie 06, 2009, 09:05:49 »

Timpul alocat întrebărilor a expirat.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #2 : Iunie 07, 2009, 11:04:15 »

As avea o intrebare, am generat numerele lu catalan, apoi din N am scazut K (parantezele care delimiteaza un mugure), iar apoi am facut o dinamica in care am cautat numarul de posibilitati de a pune N-K perechi de paranteze (asta cu ajutorul numerelor lu catalan), dar nu iau mai mult de 35. E busita ideea sau e de la implementare?
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #3 : Iunie 07, 2009, 11:28:20 »

Nu ştiu. Două inturi modulo 123457 înmulţite vor avea nevoie de long long. Ai avut grijă de asta?
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #4 : Iunie 07, 2009, 11:30:01 »

Dap, mi-am definit tot long long, si asta ma cam depaseste, ca ideea mi se pare buna Smile

Am descoperit hiba, nu prea merge generarea numerelor lui catalan modulo 123457. Imi puteti da o idee cum s-ar putea face asta? Very Happy
« Ultima modificare: Iunie 07, 2009, 11:57:57 de către Andrei Misarca » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : Iunie 07, 2009, 12:04:36 »

Folosesti invers modular.
Memorat

Am zis Mr. Green
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : Iunie 07, 2009, 14:46:58 »

Ca sa calculezi numarul de parantezari corecte cu N perechi de paranteze poti sa faci urmatoarea dinamica:

T[ i ] = suma( T[j - 1], T[i - j])  j:1->i.

De asemenea daca imi aduc eu bine aminte numerele lui Catalan parca erau o serie de combinari. Combinarile le poti calcula si fara invers modular.

C[ i ][j] = C[i - 1][j] + C[i - 1][j - 1];

Unde C[ i ][j] e combinari de i luate cate j.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #7 : Iunie 07, 2009, 21:05:40 »

Ca sa calculezi numarul de parantezari corecte cu N perechi de paranteze poti sa faci urmatoarea dinamica:
T[ i ] = suma( T[j - 1] * T[i - j])  j:1->i.

Asta chiar e o modalitate mai simpla de calculare a numerelor lui Catalan in cazul in care apare modulo. Pacat ca am pierdut 90 de puncte in concurs pe o chestie de asta, dar macar am invatat ceva din ea Smile
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines