| Fişierul intrare/ieşire: | geom2.in, geom2.out | Sursă | Selectie echipe ACM ICPC, UPB 2009 |
| Autor | Andrei Homescu | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | geom2.out |
|---|---|
| 7 3 0.1 0.2 0.3 1.0 0.8 0.9 2.0 | 5 7 |
