expozitie

[•mihai.plesa]

Salut!

Nu pricep explicatia data problemei "expozitie" de la OJI 2010: http://infoarena.ro/problema/expozitie

Descrierea oficiala a solutiei este:
Deoarece fiecare desen trebuie să apară de cel puţin k ori, ne vom asigura de acest lucru afişând fiecare desen de exact k ori, au fost ocupate astfel k*d scânduri, au mai rămas libere r=n-k*d, fiecare desen mai apare pe lângă cele k apariţii de k1, k2, …, kd ori. Dacă r=0 numărul de aranjări este 1. Dacă r<0 numărul de aranjări este 0. În celelalte cazuri considerăm ecuaţia:
k1+k2+k3+…….kd=r, 0<=ki<=r (1)
Problema se reduce la a determina numărul de soluÅ£ii ale ecuaÅ£iei (1), acest număr este egal cu combinari de (r+d-1) luate cate r . Pentru demonstraÅ£ie se reprezintă soluÅ£ia ecuaÅ£iei (1) ca o secvenţă binară, formată din k1 elemente 0, urmate de un element 1, urmat de k2 elemente 0, urmate de un element 1, ÅŸ.a.m.d., se adaugă în final kd elemente 0. ÃŽn secvenÅ£a construită sunt r elemente 0 (k1+k2+k3+…….kd=r), numărul total de elemente este n+r-1. Numărul posibilităţilor de a aranja cele r elemente 0 este combinari de (r+d-1) luate cate r   .

Puteti sa-mi explicati si mie chestia cu scrierea binara? Nu am priceput de unde le vine idea asta si de ce daca scrie cate Ki 0 si un 1 reprezinti solutia?? si pana la urma ce vor sa zica prin "reprezentam solutia"

Multumesc

[•soriyn]

Din cate tin eu minte problema asta admite si o rezolvare cu programare dinamica. E mai usor de inteles. Ar trebui sa incerci.