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

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


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

Pe o masă se află N stive (numerotate de la 1 la N). Stiva i conţine i jetoane (1≤i≤N). La o mutare se poate alege o mulţime de stive şi se pot extrage din fiecare stivă care face parte din mulţimea aleasă acelaşi număr de jetoane.

Cerinţă

Să se determine o secvenţă cu număr minim de mutări care să golească toate cele N stive.

Date de intrare

Fişierul de intrare stive.in conţine pe prima linie numărul natural N.

Date de ieşire

Fişierul de ieşire stive.out va conţine pe prima linie un număr natural MIN reprezentând minim de mutări efectuate. Pe următoarele MIN linii sunt descrise mutările, câte o mutare pe o linie. Linia ce descrie o mutare are forma:
nr s1 s2 ... snr x
unde nr reprezintă numărul de stive din mulţimea selectată la mutarea respectivă; s1, s2, ..., snr sunt stivele selectate, iar x reprezintă numărul de jetoane extrase din fiecare stivă s1, s2, ..., snr. Valorile de pe aceeaşi linie sunt separate prin spaţii.

Restricţii

1 ≤ N ≤ 30000

Exemple

stive.instive.outExplicaţii
3 2 2 2 3 2 2 1 3 1 Configuraţia iniţială a stivelor este 1 2 3
La prima mutare sunt selectate 2 stive (2 şi 3) şi se extrag câte 2 jetoane din fiecare. Se obţine configuraţia:
1 0 1
La ultima mutare se aleg stivele 1 şi 3, se extrage câte un singur jeton din fiecare şi astfel au fost golite toate stivele.

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot IS 2008: arbnr, center, pitici, sirag1, cod1, tabara, desen1, munte, pipe, euclid, sport, bombe, shgraf, paintball, arb, pav
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, turn1, carti1, program1, spioni, kgb, lift, apel, lex, 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 Divide&Impera: zeratul, reactii, cartoane, hanoi, patrate4, pav, imagine, banda, invsort, bile5, m4, xp, game1, compresie, descompunere, romb1
Software recomandat
surse trimise | ajutor