983 Expozitie

[•wefgef]

Aici puteti discuta despre problema Expozitie.

[•dornescuvlad]

Imi explica cineva solutia oficiala de dinamica va rog ? Nu e explicata deloc relatia aia de recurenta, doar trantita acolo in document, ca sa nu mai zic de aia cu combinatorica.Merci

[•stocarul]

Relația de recurență este explicată, dar probabil nu foarte explicit....
Ideea e că tu ai (i,j) = în câte feluri poți aranja pe i scânduri, oricare din primele j tipuri de desene. Tipurile vor fi puse în ordine crescătoare, deoarece 1 2 2 3 este același cu 3 2 2 1.
Acum să vedem cum obținem (i,j). Ideea e că ne bazăm pe soluția cu i-1 scânduri. Pe scândura i trebuie să punem tabloul j, tablou ce îl putem pune după oricare tip din tablourile 1,2,...,j. Deci tabloul j poate fi pus după tabloul 1 la (i-1,1), după tabloul 2 la (i-1,2), după tabloul j la (i-1,j).
Deci (i,j) = (i-1,1) + (i-1,2) + ... + (i-1,j).
Dar noi știm că (i-1,1) + (i-1,2) + ... + (i-1,j-1) este (i,j-1) (a fost calculat la coloana anterioară de pe aceeași linie). De aici rezultă că (i,j) = (i,j-1) + (i-1,j).

[•dornescuvlad]

Deci (i,j) = (i-1,1) + (i-1,2) + ... + (i-1,j).

de ce nu e (i-1,j) = (i-1,1) + (i-1,2) + ... + (i-1,j) ?

Sau de fapt nu mai conteaza, ultimul element de pe scandura i ? La fel este nr de moduri? conteaza doar modurile de la primele i-1 aranjari? Ultimul tablou este oricum >= decat celelalte si nr de moduri este acelasi ?

[•Mishu91]

Păi exact, iar acum când vrei să calculezi D[ i ][ j ], încerci să pui pe scândura i desenul j. De aceea, numărul de posibilități de a pune desenul j pe scândura i este egal cu D[ i-1 ][1] + D[ i-1][2] + ... +D[ i-1 ][j], mai precis tu pui desenul j "după" desenele 1, 2, 3, ..., j.

[•dornescuvlad]

Am formula, stiu cazurile particulare... Ce fac mai departe??? A incercat cineva sa-mi explice care o facuse de 100, dar  si-a batut joc de mine in mod sigur.. Merge rezolvarea cu un for de la i la n si apoi un for de la j la d, si sa calculez D[j]..pt ca iau 30 puncte cu rezolvarea asta si vad ca exista si numere mari.Cum fac ? Ma folosesc de cazurile particulare si folosesc un tablou tridimensional?

[•savim]

Nu cred ca raspunsurile care le-ai primit au fost bataie de joc, mai mult, din cate vad eu baietii au explicat destul de clar solutia problemei (ceea ce nu se face in deobste pe forum   ). Ar fi bine sa citesti mai atent enuntul / explicatiile si sa te straduiesti sa intelegi anumite detalii. Sunt sigur ca daca o sa te chinui un pic vei obtine 100p. Si pe viitor posteaza mai concis, daca ceri raspunsul la peste 3 intrebari simultan cel mai probabil nu o sa ti se raspunda la nici una  .

[•VisuianMihai]

Cate posibilitati exista pentru o scandura si mai mult de 2 tipuri de desene? 0 sau d?

[•AlexandruValeanu]

Daca n < d*k raspunsul este 0

[•mvcl3]

Imi explica si mie cineva care ar fi problema cu testele 6 si 8 ca nu prea imi dau seama de ce iau wa!!! ms!!