== include(page="template/taskheader" task_id="biti4") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $biti4.in$ ...
Fişierul de intrare $biti4.in$ conţine pe prima linie trei numere întregi $N$, $K$ şi $I$ cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $biti4.out$ ...
În fişierul de ieşire $biti4.out$ se va scrie pe prima linie un singur şir binar reprezentând şirul canonic căutat.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 ≤ K < N ≤ 60$
* $1 ≤ I ≤ 10^18^$
* Un şir $s = s{~1~}s{~2~}...s{~n~}$ este mai mic din punct de vedere lexicografic decât un alt şir $t = t{~1~}t{~2~}...t{~n~}$ dacă există o poziţie $p$ astfel încât $s{~p~} < t{~p~}$ şi $s{~1~} = t{~1~}$, $s{~2~} = t{~2~}$, ..., $s{~p-1~} = t{~p-1~}$.
* Întotdeauna va exista soluţie.
h2. Exemplu
table(example). |_. biti4.in |_. biti4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 2 7
| 1001
|
h3. Explicaţie
...
Cele $9$ şiruri canonice sunt: $0000$, $0001$, $0010$, $0011$, $0110$, $0111$, $1001$, $1011$, $1111$.
== include(page="template/taskfooter" task_id="biti4") ==
