Fişierul intrare/ieşire:geom2.in, geom2.outSursăSelectie echipe ACM ICPC, UPB 2009
AutorAndrei HomescuAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.225 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Geom2

O subsecventa a unui sir A este un subsir continuu de elemente din acel sir. Mai exact, o subsecventa a unui sir reprezinta valorile sirului de pe un interval de indici i, i+1, i+2, ..., j cu 1 ≤ i ≤ j ≤ N (unde N este numarul de elemente din sir). Media geometrica a unui sir de K valori reprezinta radicalul de ordin K din produsul celor K valori. De exemplu, media geometrica a valorilor 4, 9, 6 este 6.

Fiind dat un sir de N numere reale pozitive A, sa se calculeze subsecventa de lungime cel putin K si medie geometrica maxima.

Date de intrare

Pe prima linie a fisierului de intrare geom2.in se afla valorile N si K. Pe fiecare dintre urmatoarele N linii se afla cele N numere reale. Toate numerele de pe aceeasi linie vor fi separate prin cate un spatiu.

Date de ieşire

Pe singura linie a fisierului geom2.out se vor afla valorile i si j, separate printr-un spatiu, reprezentand indicii capetelor subsecventei de medie geometrica maxima si de lungime cel putin K. Daca exista mai multe solutii, puteti afisa oricare dintre ele.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ K ≤ min{N, 5.000}
  • 0 < A[i] < 1000.0
  • Pentru 70% dintre teste, K ≤ 100

Exemplu

geom2.ingeom2.out
7 3
0.1
0.2
0.3
1.0
0.8
0.9
2.0
5 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?