Fişierul intrare/ieşire:	biti4.in, biti4.out	Sursă	Summer Challenge 2009, Runda 2
Autor	Din Folclor	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Biti4

Fie mulţimea tuturor şirurilor de biţi de lungime N cu cel mult K perechi de poziţii consecutive unde cifrele 0 şi 1 sunt alăturate. Vom considera şirurile canonice ca fiind şirurile din mulţime care sunt mai mici lexicografic decât inversul lor.

Cerinţă

Considerând în ordine lexicografică toate şirurile canonice, pentru N, K şi I date, se cere să se determine al I-lea şir canonic.

Date de intrare

Fişierul de intrare biti4.in conţine pe prima linie trei numere întregi N, K şi I cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire biti4.out se va scrie pe prima linie un singur şir binar reprezentând şirul canonic căutat.

Restricţii

• 0 ≤ K < N ≤ 60
• 1 ≤ I ≤ 10¹⁸
• Un şir s = s₁s₂...s_n este mai mic din punct de vedere lexicografic decât un alt şir t = t₁t₂...t_n dacă există o poziţie p astfel încât s_p < t_p şi s₁ = t₁, s₂ = t₂, ..., s_p-1 = t_p-1.
• Întotdeauna va exista soluţie.

Exemplu

Explicaţie

Cele 9 şiruri canonice sunt: 0000, 0001, 0010, 0011, 0110, 0111, 1001, 1011, 1111.

Cum se trimit solutii?