| Fişierul intrare/ieşire: | jbird.in, jbird.out | Sursă | Concurs IQ Academy |
| Autor | Cristian Francu | Adăugată de |  Cristian Francu •francu |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 2300 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Jbird (clasa a 7-a)
J-Bird sare de pe o înălţime pe alta. Înălţimile sînt înşirate de la stînga la dreapta. J-Bird se află pe una din ele. Ea poate sări spre stînga sau spre dreapta de maxim K ori. J-Bird se întreabă cît de sus poate ajunge?
Cerinţă
Ajutaţi-o pe J-Bird să ajungă cît mai sus.
Date de intrare
Fişierul de intrare jbird.in conţine pe prima linie N, numărul de înălţimi, Q, numărul de poziţii de unde va pleca J-Bird şi K, numărul maxim de salturi pe care îl poate face J-Bird. Pe a doua linie se vor afla cele N înălţimi, separate prin spaţii, aşa cum se află ele înşirate, de la stînga la dreapta. Pe a treia linie se vor afla cele Q poziţii ale unor înălţimi de unde va pleca J-Bird (numerotate de la unu).
Date de ieşire
În fişierul de ieşire jbird.out veţi afişa Q numere. Pentru fiecare din înălţimile de plecare ale lui J-Bird veţi afişa înălţimea maximă la care poate ajunge J-Bird sărind de maxim K ori către stînga sau către dreapta.
Restricţii
- 1 ≤ N ≤ 200000
- 1 ≤ Q ≤ minim dintre N şi 100000
- 1 ≤ K ≤ 8000
- înălţimile sînt numere întregi între 1 şi 2 miliarde
- Poziţiile de unde sare J-Bird sînt numere întregi între 1 şi N
- Poziţiile de unde sare J-Bird sînt unice (nu se repetă la intrare)
Exemplu
| jbird.in | jbird.out | Explicaţii |
|---|---|---|
| 8 2 4 5 9 2 4 6 8 3 2 7 4 | 8 9 | J-Bird poate sări maxim de patru ori la stînga sau la dreapta. Cînd J-Bird sare de pe poziţia 7, de înălţime 3, va putea sări astfel: - Porneşte de la înălţime 3 - La stînga prin înălţimile 8, 6, 4, 2 din care cea mai mare înălţime este 8 - La dreapta prin înălţimea 2 din care cea mai mare înălţime este chiar 2 Deci cea mai mare înălţime la care poate ajunge J-Bird este 8 (maximul dintre 3, 2, 8) Cînd J-Bird sare de pe poziţia 4, de înălţime 4, va putea sări astfel: - Porneşte de la înălţime 4 - La stînga prin înălţimile 2, 9, 5 din care cea mai mare înălţime este 9 - La dreapta prin înălţimile 6, 8, 3, 2 din care cea mai mare înălţime este 8 Deci cea mai mare înălţime la care poate ajunge J-Bird este 9 (maximul dintre 4, 9, 8) |
