Fişierul intrare/ieşire:subset.in, subset.outSursăSelectie individuala ACM ICPC, UPB 2009
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subset

Se considera multimea {1,2,..,N}, despre care se stie ca are 2N submultimi (incluzand multimea vida). Fiecarei submultimi i se ataseaza un sir de elemente, si anume: cel mai mic sir in ordine lexicografica, format din elementele submultimii. De exemplu, submultimii {1,7,3,5} i se ataseaza sirul 1 3 5 7. Se ordoneaza toate cele 2N submultimi, in ordinea lexicografica a sirurilor asociate. De exemplu, submultimea {1,3,4,10} se va afla inaintea submultimii {1,4,5} in ordinea considerata, deoarece sirul 1 3 4 10 se afla inaintea sirului 1 4 5 in ordine lexicografica. In cazul in care sirul asociat unei submultimi cu mai putine elemente coincide cu primele elemente ale sirului asociat unei submultimi cu mai multe elemente, atunci submultimea cu mai putine elemente se considera inaintea submultimii cu mai multe elemente. De exemplu, submultimea {1,5,8,10} se afla inaintea submultimii {1,5,8,10,13,21}.

Cunoscandu-se numarul N de elemente al multimii, precum si numarul de ordine al unei submultimi in ordinea descrisa mai sus, trebuie sa afisati sirul corespunzator submultimii cu acel numar de ordine.

Date de intrare

Fişierul de intrare subset.in contine 2 valori intregi, separate printr-un spatiu, N si M, reprezentand numarul de elemente al multimii si numarul de ordine al submultimii dorite.

Date de ieşire

În fişierul de ieşire subset.out veti afisa pe o singura linie, separate prin spatii, elementele sirului asociat submultimii de pe pozitia M.

Restricţii

  • 1 ≤ N ≤ 60
  • Multimea vida nu ne intereseaza, asa ca prima submultime va fi {1}. In aceste conditii, numarul de ordine din fisierul de intrare variaza intre 1 si 2N-1 (ultima valoarea corespunzand chiar multimii {N}).
  • Aceasta problema are testele impartite in 2 grupe, valorand 30 si, respectiv, 70 de puncte.

Exemplu

subset.insubset.out
3 3
1 2 3
6 10
1 2 3 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content