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