Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | secventa.in, secventa.out | Sursă | preOJI 2004 |
Autor | Mircea Bogdan Pasoi | Adăugată de | |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Secventa
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Secventa
Gigel are un sir de N numere intregi. Toata lumea stie ca o secventa este un subsir de numere care apar pe pozitii consecutive in sirul initial. Gigel a definit baza unei secvente ca fiind minimul valorilor elementelor din secventa respectiva.
Cerinta
Fiind dat un numar natural K, determinati pentru Gigel o secventa de lungime cel putin K cu baza maxima.
Date de Intrare
Fisierul de intrare secventa.in contine pe prima linie numerele N si K, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.
Date de Iesire
Fisierul de iesire secventa.out trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de lungime cel putin K cu baza maxima si valoarea maxima a bazei.
Restrictii si precizari
S 1 <= K <= N <= 500.000
S Elementele din vector sunt numere intregi din intervalul [-30.000, 30.000]
S Daca exista mai multe solutii pentru care se obtine baza maxima, atunci se va alege cea in care pozitia de inceput a secventei este cea mai mica, iar in caz de egalitate cea in care pozitia de sfarsit a secventei este cea mai mica
Exemplu
secventa.in secventa.out Explicatie
8 3 6 8 4 Secventa care incepe pe pozitia 6 si se termina pe pozitia 8
(lungime 3) este (4, 8, 6) si are baza min(4, 8, 6) = 4.
-1 2 3 1 0 4 8 6 Nu mai exista o secventa cu lungime mai mare sau egala cu K
care sa aiba baza mai mare.