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.05 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
4 2 7
1001

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content