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

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


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

Fie un şir a1, a2, ..., aN de N numere întregi şi K un număr natural. O secvenţă ai, ai+1, ai+2 ..., aj din şir spunem că este K-secvenţă dacă există cel mult K numere strict mai mari decât ai. De exemplu, pentru N=10, şirul a = 3,6,4,2,1,10,9,5,8,7 şi K=3, atunci 6,4,2,1,10,9,5,8 este K-secvenţă pentru că sunt exact 3 numere strict mai mari decât 6. La fel, 5,8,7 este K-secvenţă pentru că sunt doar două numere mai mari strict decât 5.

Cerinţă

Scrieţi un program care să determine cea mai lungă K-secvenţă ai, ai+1, ai+2, ..., aj din şir.

Date de intrare

Fişierul de intrare ksecv.in conţine pe prima linie numerele naturale N şi K, iar pe a doua linie elementele a1 a2 ... aN ale şirului, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire ksecv.out va conţine pe prima linie linie două numere naturale i şi j separate printr-un spaţiu, reprezentând indicii de început şi de sfârşit ai K-secvenţei de lungime maximă. Dacă sunt mai multe soluţii, se va scrie aceea pentru care i este minim.

Restricţii

  • 3 <= N <= 100 000
  • 1 <= K <= N
  • -109 <= ai <= 109, pentru orice i între 1 şi N.

Exemplu

ksecv.in ksecv.out Explicaţii
10 3
3 6 4 2 1 10 9 5 8 7
2 9
Cea mai lungă 3-secvenţă este cea care începe la poziţia 2 şi se încheie la poziţia 9, adică 6 4 2 1 10 9 5 8, în această secvenţă existând 3 numere strict mai mari decât 6.
prof. Dan Pracsiu
Grupul Scolar "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Despre heap: Heap-uri
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
Despre heap: sirag, hperm, granita, gard, pitici1, cezar1, munte2, base3, sea, oldest
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, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
surse trimise | ajutor