== include(page="template/taskheader" task_id="pavare2") ==
==Include(page="template/taskheader" task_id="pavare2")==
Poveste ...
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
...
h2. Restrictii
...
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. 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. Restrictii si precizari
* $1 ≤ N ≤ 100$
* $1 ≤ A, B ≤ N$
* Se garanteaza ca exista cel putin $K$ modalitati de a pava bulevardul si $K ≥ 1$
* Pentru $50%$ din teste $K = 1$
h2. Exemplu
| pavare2.in | pavare2.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. pavare2.in |_. pavare2.out |
| 4 2 3
7
| 12
1001 |
h3. Explicatii
Cele $12$ posibilitati de pavare sunt, in ordine lexicografica :
$0010 0011 0100 0101 0110 0111 1001 1010 1011 1100 1101 1110$
Se observa ca a $7$-a posibilitate de pavare este $1001$.
== include(page="template/taskfooter" task_id="pavare2") ==
==Include(page="template/taskfooter" task_id="pavare2")==
