== include(page="template/taskheader" task_id="pavare2") ==
==Include(page="template/taskheader" task_id="pavare2")==
Poveste ...
Pavare2
In orasul Z exista un bulevard de latime 1 metru si lungime N metri care trebuie pavat. Primaria orasului dispune de placi albe si negre de 1 metru lungime si 1 metru latime in scopul pavarii bulevardului. Dupa cum va imaginati, bulevardul va fi pavat prin asezarea a N placi din stocul primariei. Pentru a alege cea mai buna metoda de pavare, primarul vrea mai intai sa stie cate moduri de pavare sunt astfel incat sa nu existe mai mult de A placi consecutive de culoare alba si B placi consecutive de culoare neagra pe bulevard. Primarul vrea sa afle apoi care este a K-a posibilitate de pavare in ordine lexicografica, stiind ca o placa alba e mai mica din punct de vedere lexicografic decat o placa neagra.
h2. Cerinta
...
Dandu-se numarul N ce reprezinta lungimea bulevardului si numerele A, B si K se cere sa se afle numarul de posibilitati de pavare ce respecta conditiile din enunt. De asemenea, se cere sa se afiseze a K-a posibilitate de pavare in ordine lexicografica, codificand cu `0' o placa alba si cu `1' o placa neagra.
h2. Date de Intrare
Pe prima linie a fisierului pavare2.in se gasesc numerele N, A, B, separate prin spatii. Pe cea de-a 2-a linie a fisierului se gaseste numarul K.
h2. Restrictii
h2. Date de Iesire
...
Pe prima linie a fisierului pavare2.out se gaseste un singur numar ce reprezinta numarul de posibilitati de pavare, iar pe cea de-a doua linie trebuie sa se afiseze pavarea ceruta codificata ca in enunt, fara a afisa spatii intre caracterele de `0' si `1'.
h2. Date de intrare
h2. Restrictii si precizari
...
- 1 <= N <= 100
h2. Date de iesire
- 1 <= A, B <= N
...
- se garanteaza ca exista cel putin K modalitati de a pava bulevardul si K >= 1
- pentru 50 de puncte se garanteaza K = 1
h2. Exemplu
| pavare2.in | pavare2.out |
| linia1
linia2
linia3
| linia1
linia2
|
pavare2.in pavare2.out Explicatii
4 2 3 12 Cele 12 posibilitati de pavare sunt, in ordine lexicografica :
7 1001 0010,
0011
0100
0101
0110
0111
1001
1010
1011
1100
1101
1110
Se observa ca a 7-a posibilitate de pavare este 1001.
References
== include(page="template/taskfooter" task_id="pavare2") ==
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/pavare2/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="pavare2")==
