|
Titlul: Sir5 Scris de: Mihai-Alexandru Dusmanu din Decembrie 27, 2012, 10:55:32 Aici se pot pune întrebări legate de problema Sir5 (http://infoarena.ro/problema/sir5) de la Runda 11 (http://infoarena.ro/monthly-2012/runda-11) a concursului Infoarena Monthly 2012.
Timpul alocat întrebărilor este de 1 ora. Î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 FARA COMENTARII. Titlul: Răspuns: Sir5 Scris de: roots1 din Decembrie 27, 2012, 12:14:47 Citat Sirul va fi dat sub forma unei vector de M Schimbati si voi "unei" cu "unui" :)) Titlul: Răspuns: Sir5 Scris de: roots1 din Decembrie 27, 2012, 12:20:47 Citat intervalele vor fi complet incluse in sir (capetele nu au voie sa depaseasca extremitatile sirului); Asta inseamna ca nu pot sa am '[' inainte de primul element din sir ? Titlul: Răspuns: Sir5 Scris de: Ionescu Vlad din Decembrie 27, 2012, 12:27:12 Spre exemplu, amplasamentul (pe exemplul din enunt):
[111]0011000 este valid. (Incepe in sir pe pozitia 1 si se termina pe pozitia 3). Titlul: Răspuns: Sir5 Scris de: Oncescu Costin din Decembrie 27, 2012, 13:38:53 Cum se facea problema asta m-am chinuit cu niste porcarii de dinamici 3D dar nu mergea.Puteti sa imi spuneti si mie?
Multumesc anticipat. Titlul: Răspuns: Sir5 Scris de: Adrian Craciun din Decembrie 27, 2012, 13:41:35 Probabil dinamica cu inmultire de matrici :D
Titlul: Răspuns: Sir5 Scris de: Alex Velea din Decembrie 27, 2012, 15:14:52 Cred ca poti sa o iei asa ..
Consideri Ca inlantuiesti bitii aia .. Daca ai 3 3 3 4 o sa iti faci 1110001110000 .. smenul e ca l < 30 .. Deci poti sa o iei ca fiind 111000[ inca multi de 0 ] 0000111100000[multi de 0]00111111[multi de 1]111100 etc. Sper ca te-ai prins de idee .. Daca ai un "sir" de 1 .. il iei ca 1111 ( 30 maxim .. ( L adica ) ) .. MULTI DE 1 .. 111 ( 30 maxim ). De ce faci asta? Pentru ca daca ai 001111 ( sa zicem la pasul x ) ca sa treci la pasul x+1 iti scoti tu acolo o dinamica. Si la dinamica aia iti trebuie doar 30 de pasi din recurenta. Sau L .. sau ceva de genu. Si cand ai 1111111 ( multi ) ultimi 30 sunt 1 .. si la pasul x+1 .. x+2 .. etc o sa fie aceeasi recurenta. Si poti scoate acolo dinamica cu inmultiri de matrici, cum a zis Adi.. Daca desfasori tot pe acolo o sa ai cam 100 de caractere + ceva inmultire de matrici care merge repede :rotfl: Sper ca ai inteles ^^ Succes in continuare >:D< Titlul: Răspuns: Sir5 Scris de: Laurentiu Mihai din Decembrie 27, 2012, 15:21:53 Cum se facea problema asta m-am chinuit cu niste porcarii de dinamici 3D dar nu mergea.Puteti sa imi spuneti si mie? Multumesc anticipat. Salut, Nu am rezolvat-o, dar cred ca ar putea ajuta ideile urmatoare: - daca la un moment-dat numarul de 0-uri consecutive e mai mic decat L, atunci acele 0-uri pot fi considerate tot 1-uri. - daca la un moment-dat numarul de 0-uri consecutive e >= L, atunci trebuie combinate 'cumva' grupurile 11..1, 0..0, 1..1 (bazandu-ne pe faptul ca 0-urile sunt cel putin L, deci nu exista segment care sa treaca din primul grup de 1-uri pana la celalalt grup de 1-uri), poate folosind ceva de genul N[ i ][ j ] = numarul de pavari in care primul segment incepe de la pozitia -i (minus i), iar ultimul se termina la lungime_sir+j - daca am avea aceste valori pentru cele doua siruri de 1-uri, atunci cred ca s-ar putea calcula aceste valori si pentru sirul cu 0-uri la mijloc. (s.a.m.d., iar la final de tot interesandu-ne solutia cu i=j=0) Mi-ar placea sa vad idei mai simple. |