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:
data fiind o submultime, sa se determine numarul ei de ordine;
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:
pe prima linie numarul natural n;
pe a doua linie un numar natural m, reprezentând
numarul de operatii ce trebuie executate;
pentru fiecare operatie urmeaza în fisier câte doua linii; pe prima linie dintre cele
doua este scris tipul operatiei (1
sau 2); daca tipul operatiei
este 1, atunci pe cea de a
doua linie este scris numarul de elemente din submultime, urmat de elementele
submultimii, separate prin spatii; daca tipul operatiei este 2,
pe cea de a doua linie va fi scris un numar de ordine (adica un numar natural
cuprins între 1 si
2n-1).
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
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil"
Iasi