Catalin Moje: Pagină nouă: ==Enunț== Se consideră trei numere naturale nenule n, k și w. ==Cerința== Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2], … ,x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile: 1 ≤ x[1] < x[2] < ... < x[k] ≤ n x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1 ==Date de intrare== Fișierul de intrare nmult.in conține pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu se...

2023-05-07T17:59:12Z

Pagină nouă: ==Enunț== Se consideră trei numere naturale nenule n, k și w. ==Cerința== Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2], … ,x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile: 1 ≤ x[1] < x[2] < ... < x[k] ≤ n x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1 ==Date de intrare== Fișierul de intrare nmult.in conține pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu se...

New page

==Enunț==
Se consideră trei numere naturale nenule n, k și w.

==Cerința==
Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2], … ,x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile:

1 ≤ x[1] < x[2] < ... < x[k] ≤ n
x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1

==Date de intrare==
Fișierul de intrare nmult.in conține pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu semnificaţia de mai sus.

==Date de ieșire==
Fișierul de ieșire nmult.out va conține pe prima linie restul împărţirii numărului m la 666013.

==Restricții și precizări==

1 ≤ n, k, w ≤ 1.000.000;

==Exemplu==
===Exemplu1===

nmult.in
<syntaxhighlight lang="python">
5 2 2
</syntaxhighlight>

nmult.out
<syntaxhighlight lang="python">
6
</syntaxhighlight>

===Exemplu2===
nmult.in
<syntaxhighlight lang="python">
10 3 4
</syntaxhighlight>

nmult.out
<syntaxhighlight lang="python">
4
</syntaxhighlight>

===Exemplu3===
nmult.in
<syntaxhighlight lang="python">
10 4 4
</syntaxhighlight>

nmult.out
<syntaxhighlight lang="python">
0
</syntaxhighlight>

==Rezolvare==
<syntaxhighlight lang="python">

def validare(n, k, w):
if not(1 <= n <= 1000000 and 1 <= k <= 1000000 and 1 <= w <= 1000000):
return False
return True

def rezolvare(n, k, w):
MOD = 666013
# Cazul de bază
if k == 1:
return n

# Cazul în care diferența minimă între elemente este mai mare decât n
if w >= n:
return 0

# Aplicăm formula de recursivitate
dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][1] = 1
for j in range(2, k + 1):
for i in range(1, n + 1):
dp[i][j] = (dp[i - 1][j] + dp[max(0, i - w)][j - 1]) % MOD

# Suma soluțiilor pentru mulțimile de k elemente
sol = 0
for i in range(1, n + 1):
sol = (sol + dp[i][k]) % MOD

return sol

def main():
with open("nmult.in", "r") as fin:
n, k, w = map(int, fin.readline().split())

if not validare(n, k, w):
print("Date de intrare invalide")
return

m = rezolvare(n, k, w)

with open("nmult.out", "w") as fout:
fout.write(str(m) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicații ==
Codul are trei funcții principale:

Funcția validare primește parametrii n, k și w și verifică dacă aceștia sunt în intervalul valid (între 1 și 1000000). Dacă parametrii nu sunt în intervalul valid, se returnează False, altfel se returnează True.

Funcția rezolvare primește parametrii n, k și w. În primul rând, se verifică cazurile speciale. Dacă k == 1, atunci numărul de mulțimi posibile este n. Dacă w >= n, atunci nu există nicio mulțime de k elemente cu diferența între oricare 2 termeni consecutivi mai mare sau egală cu w, așadar numărul de mulțimi posibile este 0.

În cazul general, se aplică formula de recursivitate pentru a calcula numărul de mulțimi posibile. Mai precis, se calculează matricea dp, unde dp[i][j] reprezintă numărul de mulțimi de j elemente care se termină cu numărul i și ale căror diferențe între oricare 2 termeni consecutivi sunt cel puțin w. Acest lucru se realizează cu ajutorul formulei: dp[i][j] = dp[i-1][j] + dp[max(0, i-w)][j-1].

În cele din urmă, se calculează suma soluțiilor pentru toate mulțimile de k elemente, care încep cu elementul 1 până la elementul n-w+1.

Funcția main citește datele de intrare din fișierul nmult.in și le validează cu ajutorul funcției validare. Apoi, calculează soluția problemei cu ajutorul funcției rezolvare și o scrie în fișierul nmult.out.

1195 - NMult - Revision history