.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » lex

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
lex


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

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:
  • 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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, joc7, cuburi1, sant, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
Software recomandat
surse trimise | ajutor