Fișierul intrare/ieșire jbird.in, jbird.out Sursă Concurs IQ Academy
Autor Cristian Frâncu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.25 sec Limită de memorie 2300 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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)

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii