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

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


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

Se consideră un şir x1, x2, ..., xn format din n numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma xi,xi+1,...,xk-1,xk,xk+1,...,xj (1≤i<k<j≤n) cu proprietatea că xi<xi+1<...< xk-1<xk>xk+1>...>xj, se numeşte munte cu vârful xk. Două secvenţe munte au maxim un element comun în şir. O secvenţă munte are cel puţin 3 elemente. Un exemplu de şir format cu valorile 3 4 6 8 nu conţine nicio secvenţă munte, iar unul format cu valorile 3 4 8 1 2 5 0 conţine 2 secvenţe munte: 3 4 8 1 şi 1 2 5 0.
După determinarea tuturor secvenţelor munte şi a vârfurilor acestora, se elimină din şir vârfurile secvenţelor munte şi procedura continuă repetat cu determinarea noilor secvenţe munte şi a vârfurilor lor din şirul nou obţinut. Procedura se opreşte în momentul în care în şir nu mai există nicio secvenţă munte.

Cerinţă

Scrieţi un program care citeşte numerele n, x1, x2, ..., xn şi apoi determină:
a) numărul de secvenţe munte din şirul iniţial;
b) numărul total de secvenţe munte obţinute pornind de la şirul iniţial până la cel care nu mai conţine nicio secvenţă munte;
c) numărul de elemente din şirul final care nu mai conţine secvenţe munte.

Date de intrare

Fişierul de intrare munte3.in conţine pe prima linie numărul natural n, iar pe următoarea linie numerele naturale x1, x2, ..., xn separate două câte două prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire munte3.out va conţine pe prima linie un număr natural conform cerinţei a), pe a doua linie un număr natural conform cerinţei b), pe a treia linie un număr natural conform cerinţei c).

Restricţii

3 ≤ n ≤ 100
0 ≤ xi ≤ 100000, 1 ≤ i ≤ n
• Pentru testele date se asigură că şirul de numere dat iniţial conţine cel puţin o secvenţă munte.

Exemple

munte3.inmunte3.outExplicaţii
8 1 2 5 0 6 9 3 4 2 4 4 a) Sunt două secvenţe munte: 1 2 5 0 şi 0 6 9 3
b) După eliminarea vârfurilor secvenţelor munte, şirul nou este 1 2 0 6 3 4. Acest şir conţine 2 secvenţe munte: 1 2 0 şi 0 6 3. După eliminarea vârfurilor secvenţelor munte, şirul nou este 1 0 3 4. Noul şir nu mai conţine nicio secvenţă munte. În total sunt deci 4 secvenţe.
c) Şirul final care nu mai conţine secvenţe munte 1 0 3 4 are 4 elemente

autor: Prof. Roxana Tîmplaru
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OJI 2014: arrows, tcif, imprimanta, ferma1, triunghi6, cartite, fractii2, cool, pseudobil, martisoare, piramide, patrat1, schi1
De acelaşi autor: numere4, tablou, numar1, prieteni2, roboti, numere6, cartonas, test1, v, cuvant, roboti1, asfalt, grupe2, joc17, numar5
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, 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, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor