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

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


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

Ionică are o cutie plină cu cuburi. Pe fiecare cub este scrisă o cifră. La un moment dat Ionică aşează n cuburi unul peste altul formând un turn. Tatăl lui Ionică văzând turnul îi spune o cifră k şi o modalitate de scoatere a unor cuburi din turn. Mai precis Ionică trebuie să scoată cuburi pentru a obţine un turn cu înăţimea minimă după următoarele reguli:
• la un moment dat se poate scoate o grupă cu cel puţin k cuburi alăturate care au pe ele scrise aceeaşi cifră;
• grupele se elimină începând de la baza turnului, de fiecare dată începând cu prima grupă ce respectă condiţia anterioară.

Cerinţă

Să se scrie un program care să determine turnul final, după eliminarea tuturor grupelor de cuburi conform modalităţii precizate de tatăl lui Ionică.

Date de intrare

Fişierul de intrare turn.in are pe prima linie numerele naturale n şi k separate printr-un spaţiu, iar pe linia următoare cifrele scrise pe cuburi în ordine de la baza cubului spre vârf, separate între ele prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire turn.out va conţine pe prima linie numărul de cuburi din turnul cerut, iar a doua linie cifrele de pe cuburile turnului (în ordine de la baza turnului până la vârful său) cu un spaţiu între spaţiu între ele.

Restricţii

2 <= n <= 49000
2<= k <= 9

pentru toate testele turnul rezultat are cel puţin un cub

Exemple

turn.inturn.outExplicaţii
20 3 1 0 2 2 2 0 0 0 7 7 5 5 5 5 5 7 7 7 3 9 3 1 3 9 Evoluţia turnului este următoarea:
După eliminarea grupului de cuburi cu cifrele
2 2 2 se obţine:
1 0 0 0 0 7 7 5 5 5 5 5 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
0 0 0 0 se obţine:
1 7 7 5 5 5 5 5 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
5 5 5 5 5 se obţine:
1 7 7 7 7 7 3 9
După eliminarea grupului de cuburi cu cifrele
7 7 7 7 7 se obţine:
1 3 9

21 4 1 2 2 2 2 1 1 3 3 3 3 3 1 1 4 4 4 4 4 1 1 2 1 1 Evoluţia turnului este următoarea:
După eliminarea grupului de cuburi cu cifrele
2 2 2 2 se obţine:
1 1 1 3 3 3 3 3 1 1 4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
3 3 3 3 3 se obţine:
1 1 1 1 1 4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
1 1 1 1 1 se obţine:
4 4 4 4 4 1 1
După eliminarea grupului de cuburi cu cifrele
4 4 4 4 4 se obţine:
1 1


autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, maxq, tric, cover, dist, munte1, promo, puncte1, role
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, creioane, exp, donald, young, albine, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, covor, pavari, parcela, grad1, ec, stalpi2, grad2, testament, nrpomi, elicop, triburi1, showroom, cartite
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, 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, matriosca, 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