Fişierul intrare/ieşire:pavare2.in, pavare2.outSursăpreONI 2006 Runda 3
AutorDaniel PasailaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content