1195 - NMult

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.