AjM: Pagină nouă: == Enunt == 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...

2024-06-03T15:57:52Z

Pagină nouă: == Enunt == 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...

New page

== Enunt ==
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.
== Cerinţa ==
Determinaţi timpul minim în care Pikachu poate îndeplini această sarcină.
== Date de intrare ==
Fișierul de intrare pikachu.in 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 şi precizări ==
* 1 ≤ N ≤ 100.000
* 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.in
5 3
5 2 4 3 7
; pikachu.out
2
<br>

== 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.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_time_to_consecutive_height(N, K, heights):
min_time = float('inf')
counter = {}
start, end = 0, 0

while end < N:
height = heights[end]
counter[height] = counter.get(height, 0) + 1
end += 1

while len(counter) > 1 or (len(counter) == 1 and max(counter.values()) < K):
start_height = heights[start]
counter[start_height] -= 1
if counter[start_height] == 0:
del counter[start_height]
start += 1

if len(counter) == 1 and max(counter.values()) >= K:
min_time = min(min_time, end - start)

return min_time

def main():
with open("pikachu.in", "r") as fin, open("pikachu.out", "w") as fout:
N, K = map(int, fin.readline().split())
heights = list(map(int, fin.readline().split()))
min_time = min_time_to_consecutive_height(N, K, heights)
fout.write(str(min_time) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4019 - Pikachu - Revision history