| Fişierul intrare/ieşire: | subset.in, subset.out | Sursă | Selectie individuala ACM ICPC, UPB 2009 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | subset.out |
|---|---|
| 3 3 | 1 2 3 |
| 6 10 | 1 2 3 6 |
