2358 - castig

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>