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

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)