4284 - Kx Desc: Diferență între versiuni
Mraa (discuție | contribuții) (Pagină nouă: Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x. ==Cerința== Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen. ==Date de intrare== Fișie...) |
Mraa (discuție | contribuții) Fără descriere a modificării |
||
Linia 31: | Linia 31: | ||
3184 | 3184 | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
MOD = 10007 | MOD = 10007 | ||
def kx_descompuneri(n, k, x): | def kx_descompuneri(n, k, x): | ||
dp = [[0] * (x + 1) for _ in range(n + 1)] | |||
for i in range(x + 1): | |||
dp[i][i] = 1 | |||
for i in range(x + 1, n + 1): | |||
for j in range(1, x + 1): | |||
dp[i][j] = (dp[i - 1][j - 1] + dp[i - x - 1][j]) % MOD | |||
rezultat = 0 | |||
for i in range(n - x + 1, n + 1): | |||
rezultat = (rezultat + dp[i][x]) % MOD | |||
return rezultat | |||
if __name__ == "__main__": | |||
# Citim datele de intrare | |||
n, k, x = map(int, input().split()) | |||
# Calculăm rezultatul și îl afișăm | |||
rezultat = kx_descompuneri(n, k, x) | |||
print(rezultat) | |||
</syntaxhighlight> | |||
Versiunea curentă din 11 ianuarie 2024 17:43
Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.
Cerința
Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.
Date de intrare
Fișierul de intrare kx_desc.in conține pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.
Date de ieșire
Fișierul de ieșire kx_desc.out va conține o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.
Restricții și precizări
Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000; 1 ≤ x, k ≤ n ==Exemplul 1==: kx_desc.in
20 2 3 kx_desc.out
8
Explicație
Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12.
==Exemplul 2==: kx_desc.in
2000 19 7 kx_desc.out
3184
Rezolvare
MOD = 10007
def kx_descompuneri(n, k, x):
dp = [[0] * (x + 1) for _ in range(n + 1)]
for i in range(x + 1):
dp[i][i] = 1
for i in range(x + 1, n + 1):
for j in range(1, x + 1):
dp[i][j] = (dp[i - 1][j - 1] + dp[i - x - 1][j]) % MOD
rezultat = 0
for i in range(n - x + 1, n + 1):
rezultat = (rezultat + dp[i][x]) % MOD
return rezultat
if __name__ == "__main__":
# Citim datele de intrare
n, k, x = map(int, input().split())
# Calculăm rezultatul și îl afișăm
rezultat = kx_descompuneri(n, k, x)
print(rezultat)