lex

Sa consideram n obiecte, numerotate de la 1 la n. Din cele n obiecte se pot forma 2n-1 submultimi distincte nevide. Daca ordonam submultimile lexicografic putem asocia fiecarei submultimi un numar de ordine de la 1 la 2n-1.

De exemplu, pentru n=3 submultimile nevide în ordine lexicografica sunt:

Submultimea {1} {1, 2} {1, 2, 3} {1, 3} {2} {2, 3} {3}
Nr. de ordine 1 2 3 4 5 6 7
In multe aplicatii practice este necesara implementarea eficienta a urmatoarelor doua operatii:
  1. data fiind o submultime, sa se determine numarul ei de ordine;
  2. dat fiind un numar de ordine, sa determine submultimea corespunzatoare.

Cerinta

Scrieti un program care sa implementeze cele doua operatii!

Date de intrare

Fisierul de intrare lex.in contine: Date de iesire

Fisierul de iesire lex.out va contine m linii, câte una pentru fiecare operatie din fisierul de intrare. Pe fiecare linie va fi scris rezultatul unei operatii, în ordinea în care operatiile apar în fisierul de intrare. Daca operatia este de tip 1, în fisierul de iesire va fi afisat numarul de ordine al submultimii specificate în operatie. Daca operatia este de tip 2, în fisierul de iesire vor fi afisate elementele submultimii cu numarul de ordine specificat, separate prin spatii, în ordine crescatoare.

Restrictii

1 <= n <= 30
1 <= m <= 1000

Exemple
lex.in lex.out
3
3
2
3
1
2 2 3
2
7
 1 2 3
6
3
Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez

Liceul de Informatica "Grigore Moisil" Iasi

Contact:ema at mail.dntis.ro