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

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


Timp maxim de execuţie/test:
0.1 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB

Toată lumea cunoaşte celebrele păpuşi de lemn, care încap una în alta, numite matrioşca.

matriosca

La atelierul unde se confecţionează aceste păpuşi lucrează mai mulţi meşteri, fiecare meşter lucrând numai păpuşi de aceiaşi înălţime. Fiecare meşter, cum termină o păpuşă o aşează pe o bandă rulantă, care duce păpuşile spre secţia de împachetare. Aici lucrează numai Gigel, care ia fiecare păpuşă, în ordinea în care le aduce banda rulantă, şi o aşează fie în una din păpuşile deja sosite, dacă este posibil, fie separat, dacă acest lucru nu este posibil. O păpuşă poate fi introdusă în alta doar dacă înălţimea primeia este strict mai mică decât a celei de a doua.

Cerinţă

Să se determine numărul minim de seturi de păpuşi pe care Gigel le poate forma în procesul de împachetare.

Date de intrare

Prima linie a fişierului de intrare matriosca.in conţine un singur număr natural n, reprezentând numărul păpuşilor de pe banda rulantă. Următoarele n linii conţin fiecare câte un număr natural, reprezentând înălţimile păpuşilor, în ordinea sosirii lor pe bandă la secţia de împachetare.

Date de ieşire

Pe prima linie a fişierului de ieşire matriosca.out se va scrie numărul nrm de seturi de păpuşi împachetate. Următoarele nrm linii vor conţine, fiecare, numărul de păpuşi din setul respectiv, urmat de numerele de ordine ale păpuşilor pe care Gigel le-a pus în set, în ordinea sosirii lor pe bandă.

Restricţii

0<n<2501
înălţimile păpuşilor sunt numere naturale strict pozitive < 2000000000

Exemplu

matriosca.in matriosca.out Explicaţii
10
4
1
5
10
7
9
2
8
3
2
4
2 1 2
2 3 7
4 4 5 9 10
2 6 8
Pot fi formate 4 seturi de păpuşi matrioşca:
setul 1: din 2 păpuşi: 1 şi 2
setul 2: din 2 păpuşi: 3 şi 7
setul 3: din 4 păpuşi: 4,5,9 şi 10
setul 4: din 2 păpuşi: 6 şi 8
O altă soluţie posibilă:
4
2 1 2
3 3 9 10
3 4 5 7
2 6 8
prof. Marinel Şerban
Liceul de Informatică „Grigore Moisil” Iaşi
marinel_serban@yahool.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor