Fişierul intrare/ieşire:pikachu.in, pikachu.outSursăONI 2009, clasele 11-12
AutorAndrei GrigoreanAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pikachu

Miruna şi partenerul ei de aventură, Pikachu, sunt în faţa unei noi provocări. Cele două personaje au ajuns lângă un lanţ muntos format din N vârfuri aşezate în linie dreaptă unul după altul. Pentru fiecare vârf muntos se cunoaşte înălţimea lui. Folosindu-se de puterile sale extraordinare, Pikachu este capabil sa scadă sau să crească înălţimea unui vârf muntos cu o unitate într-o secundă. Din motive necunoscute muritorilor de rând, cei doi prieteni vor să obţină cel puţin K vârfuri montane consecutive care au aceeaşi înălţime, într-un timp cât mai scurt.

Determinaţi timpul minim în care Pikachu poate îndeplini această sarcină.

Date de intrare

Fişierul de intrare pikachu.in va conţine pe prima linie două numere N şi K având semnificaţia din enunţ. Pe cea de a doua linie se vor găsi N numere naturale reprezentând înălţimile vârfurilor muntoase.

Date de ieşire

Fişierul de ieşire pikachu.out va conţine un singur număr natural T, reprezentând timpul minim necesar pentru a obţine cel puţin K vârfuri consecutive cu aceeaşi înălţime.

Restricţii

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ N
  • Înălţimile munţilor sunt numere pozitive care se pot reprezenta pe întregi de 32 de biţi cu semn
  • 20% din teste au 1 ≤ N, K ≤ 100, iar înălţimile aparţin intervalului [1, 100]
  • Alte 20% din teste au 1 ≤ N, K ≤ 5000
  • Rezultatul se poate reprezenta pe un întreg de 64 biţi cu semn

Exemplu

pikachu.inpikachu.out
5 3
5 2 4 3 7
2

Explicaţie

În prima secundă se creşte înălţimea muntelui de pe poziţia a doua, iar în a doua secundă se scade înălţimea muntelui de pe poziţia a treia. În urma acestor operaţii subsevenţa care începe pe a doua poziţie şi se termină pe a patra poziţie va conţine doar vârfuri de înălţime 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content