Revizia anterioară Revizia următoare
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
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Link: [1]File-List
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 de puncte se garanteaza K = 1
Exemplu
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