Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-07-28 21:21:26.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:biti4.in, biti4.outSursăSummer Challenge 2009, Runda 2
AutorDin FolclorAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 ≤ 1018
  • Un şir s = s1s2...sn este mai mic din punct de vedere lexicografic decât un alt şir t = t1t2...tn dacă există o poziţie p astfel încât sp < tp şi s1 = t1, s2 = t2, ..., sp-1 = tp-1.
  • Întotdeauna va exista soluţie.

Exemplu

biti4.inbiti4.out
3 2 3
010

Explicaţie

Cele 6 şiruri canonice sunt: 000, 001, 010, 011, 101, 111.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?