0730 - Minus K

Cerința

Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.

Date de intrare

Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 2011.

Restricții și precizări

1 ≤ K ≤ N ≤ 1000000; pentru 30% dintre teste N ≤ 10 pentru 70% dintre teste N ≤ 1000 ==Exemplu==: minusk.in

4 2 minusk.out

8

Explicație

Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.

Rezolvare

MOD = 2011

def numar_siruri(N, K):

   # Inițializăm matricea dp cu 0-uri
   dp = [[0] * 2 for _ in range(N + 1)]
   # Prima coloană este 1, pentru că există un singur șir de lungime 0, și anume șirul vid
   dp[0][0] = 1
   # Calculăm numărul de șiruri
   for i in range(1, N + 1):
       # Dacă adăugăm + în șirul anterior, nu adăugăm un semn - pe poziția i
       dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
       # Dacă adăugăm - în șirul anterior, verificăm dacă am adăugat deja K semne - consecutive
       if i >= K:
           dp[i][1] = (dp[i - 1][0] - dp[i - K][1] + MOD) % MOD
       else:
           dp[i][1] = dp[i - 1][0]
   return (dp[N][0] + dp[N][1]) % MOD

if __name__ == "__main__":

   with open("minusk.in", "r") as f:
       N, K = map(int, f.readline().split())
   rezultat = numar_siruri(N, K)
   with open("minusk.out", "w") as g:
       g.write(str(rezultat) + "\n")