3940 - Low Mem

Cerinţa

Se dă un șir cu n elemente, numere naturale și un număr k. Să se determine câte secvențe din șir au lungimea k și sunt formate din valori mai mici sau egale cu t, unde t este ultimul element al șirului.

Date de intrare

Fișierul de intrare lowmem.in conține pe prima linie numerele n și k, iar pe cea de-a doua linie cele n elemente ale șirului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", iar fișierul de ieșire lowmem.out va conține valoarea nrs, reprezentând numărul secvențelor din șir de lungime k, care sunt formate din valori mai mici sau egale cu t. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ n ⩽ 1.000
• elementele șirului vor fi mai mici sau egale decât 2.000.000.000.

Exemple

Exemplul 1

lowmen.in

8 3

1 4 3 5 7 3 4 5

lowmen.out

Datele sunt introduse corect.

9 6

8 2 7

Exemplul 2

lowmem.in

5 2

10 9 8 7 6

lowmem.out

Datele sunt introduse corect.

3 4

9 10

Exemplul 3

lowmem.in

10 12

1 2 3 4 5 6 7 8 9 10

lowmem.out

Datele nu corespund restricțiilor impuse.

0

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 3940 - Low Mem

def validare(n, k, sir):

   if not (1 <= n <= 1000000 and 1 <= k <= n):
       return False
   if len(sir) != n:
       return False
   if any(x > 2000000000 for x in sir):
       return False
   return True

def rezolvare(n, k, sir):

   t = sir[-1]
   nrs = 0
   for i in range(n - k + 1):
       if max(sir[i:i+k]) <= t:
           nrs += 1
   return nrs

def main():

   try:
       with open("lowmem.in") as f:
           n, k = map(int, f.readline().split())
           sir = list(map(int, f.readline().split()))
   except:
       print("Datele nu corespund formatului cerut.")
       return

   if not validare(n, k, sir):
       print("Datele nu corespund restricțiilor impuse.")
       return

   nrs = rezolvare(n, k, sir)

   print(f"{nrs} {n-k+1}")
   with open("lowmem.out", "w") as f:
       f.write(str(nrs) + "\n")
       f.write(" ".join(str(x) for x in sorted(sir)[-k:]) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>