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

<syntaxhighlight lang="python3"> 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")

</syntaxhighlight>