==Include(page="template/taskheader" task_id="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.

 
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.

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

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$.

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

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$.

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$

- 1 <= N <= 100
 
- 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

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$.

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
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/pavare2/enunt_files/filelist.xml

==Include(page="template/taskfooter" task_id="pavare2")==

794