Fişierul intrare/ieşire: | pavare2.in, pavare2.out | Sursă | preONI 2006 Runda 3 |
Autor | Daniel Pasaila | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
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.
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.
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.
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
Exemplu
pavare2.in | pavare2.out |
---|---|
4 2 3 7 | 12 1001 |
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.