Andrada378: Pagină nouă: == Enunț == Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea. La concurs există n premii, numerotate de la 1 la n, în ordinea în care sunt aşezate pe masă. Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact k premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el k premii aşezate pe poziţii consecutive...

2024-01-03T12:48:09Z

Pagină nouă: == Enunț == Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea. La concurs există n premii, numerotate de la 1 la n, în ordinea în care sunt aşezate pe masă. Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact k premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el k premii aşezate pe poziţii consecutive...

New page

== Enunț ==
Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea. La concurs există n premii, numerotate de la 1 la n, în ordinea în care sunt aşezate pe masă. Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact k premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el k premii aşezate pe poziţii consecutive dintre cele rămase după ce a ales Ana. Ana este foarte supărată pe Bogdan, aşa că ea urmăreşte ca Bogdan să câştige cât mai puţin, fără să o intereseze prea mult ce premii alege ea.

== Cerința ==
Scrieţi un program care, cunoscând n, k şi valorile celor n premii, determină cel mai mic număr valmin, astfel încât Bogdan să nu poate selecta k premii aşezate pe poziţii consecutive cu o valoare totală mai mare decât valmin.

== Date de intrare ==
Fișierul de intrare castigin.txt conţine pe prima linie două numere naturale n k, reprezentând numărul total de premii şi respectiv numărul de premii consecutive pe care câştigătorii trebuie să le aleagă. Pe a doua linie se află n numere naturale v[1], v[2], …, v[n] reprezentând, în ordinea aşezării pe masă, valorile celor n premii.

== Date de ieșire ==
Fișierul de ieșire castigout.txt va conţine o singură linie pe care va fi scris numărul natural valmin, determinat conform cerinţei.

== Restricții și precizări ==

* 3 ≤ n ≤ 100 000
* 1 ≤ k ≤ n/3
* 1 ≤ v[i] ≤ 1 000 000 000, pentru 1 ≤ i ≤ n

== Exemplu: ==
'''castigin.txt'''

10 3

2 5 7 3 1 22 7 2 9 1

'''castigout.txt'''

15

== Explicație ==
Dacă Ana alege premiile cu valorile 1 22 7, secvenţa cea mai convenabilă pentru Bogdan este 5 7 3 (deci valmin este 15). Există şi alte alegeri bune pentru Ana (22 7 2), dar valmin rămâne acelaşi.

== Rezolvare ==
<syntaxhighlight lang="python">
def este_input_valid(n, k, v):
if not (3 <= n <= 100000):
return False

if not (1 <= k <= n // 3):
return False

for i in range(n):
if not (1 <= v[i] <= 1000000000):
return False

return True

def gaseste_valoarea_minima():
nmax = 100002

fin = open("castigin.txt", "r")
fout = open("castigout.txt", "w")

n, k = map(int, fin.readline().split())
v = list(map(int, fin.readline().split()))

if not este_input_valid(n, k, v):
print("Input invalid. Verificați condițiile.")
return

s = [0] * nmax
smax = [0] * nmax
dmax = [0] * nmax

suma_val = sum(v[:k])
s[0] = smax[0] = suma_val

for i in range(1, n - k + 1):
s[i] = s[i - 1] - v[i - 1] + v[i + k - 1]
smax[i] = smax[i - 1] if s[i] <= smax[i - 1] else s[i]

dmax[n - k] = s[n - k]

for i in range(n - k - 1, 0, -1):
dmax[i] = dmax[i + 1] if s[i] <= dmax[i + 1] else s[i]

valmin = dmax[k + 1]

for i in range(2, k + 1):
if valmin > dmax[i + k]:
valmin = dmax[i + k]

for i in range(k + 1, n - k + 1):
maxim = smax[i - k] if smax[i - k] > dmax[i + k] else dmax[i + k]
if maxim < valmin:
valmin = maxim

fout.write(str(valmin) + '\n')

fin.close()
fout.close()

if __name__ == "__main__":
gaseste_valoarea_minima()
</syntaxhighlight>

2358 - castig - Revision history