Fişierul intrare/ieşire:jbird.in, jbird.outSursăConcurs IQ Academy
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.25 secLimită de memorie2300 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.injbird.outExplicaţ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 5, de înălţime 6, va putea sări astfel:
- Porneşte de la înălţime 6
- La stînga prin înălţimile 4, 2, 9, 5 din care cea mai mare înălţime este 9
- La dreapta prin înălţimile 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 6, 9, 8)
Trebuie sa te autentifici pentru a trimite solutii. Click aici