2532 - Cnt Cif Sum

Cerința

Se dă un număr N și un număr S. Să se determine câte numere de N cifre au suma cifrelor S.

Date de intrare

Programul citește de la tastatură numerele N și S.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând numărul de numere de N cifre având suma cifrelor S modulo 666013.

Restricții și precizări

1 ≤ N ≤ 1000 1 ≤ S ≤ 9 * N ==Exemplu==: Intrare

2 3 Ieșire

3

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 666013

def numere_suma(N, S):

  dp = [[0] * (S + 1) for _ in range(N + 1)]
  # Inițializăm prima coloană cu 1, deoarece există o singură modalitate de a obține suma 0
  for i in range(N + 1):
      dp[i][0] = 1
  # Calculăm numărul de moduri
  for i in range(1, N + 1):
      for j in range(1, S + 1):
          for k in range(10):
              if j - k >= 0:
                  dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD
  return dp[N][S]

if __name__ == "__main__":

  N, S = map(int, input("Introduceți N și S separate prin spațiu: ").split())
  
  rezultat = numere_suma(N, S)
  
  print(rezultat)

</syntaxhighlight>