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")
python minusk.py