2532 - Cnt Cif Sum: Difference between revisions
Pagină nouă: ==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,... |
No edit summary |
||
| Line 19: | Line 19: | ||
3 | 3 | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
MOD = 666013 | MOD = 666013 | ||
def numere_suma(N, S): | 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> | |||
Revision as of 17:34, 11 January 2024
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"> 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>