Editing 3240 - Sequences

==Cerința==
Să se calculeze numărul de șiruri crescătoare de lungime n, cu numere de la 1 la m, în care fiecare element apare de cel mult k ori.

==Date de intrare==
De la intrarea standard se citesc numerele întregi n, m și k, separate prin spațiu.

==Date de ieșire==
La ieșirea standard programul va afișa numărul de șiruri descrise în enunț.

==Restricții și precizări==
0 < n < 31
0 < m < 31
0 < k < 31
==Exemplu==:
Intrare

3 4 2
Ieșire

16
==Explicație==
Explicație. Șirurile sunt: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4).
==Rezolvare==
<syntaxhighlight lang="python3" line="1">
def numar_siruri(n, m, k):

   # Funcție auxiliară pentru calculul coeficientului binomial
   def comb(n, r):
       result = 1
       for i in range(r):
           result = (result * (n - i)) // (i + 1)
       return result
   # Funcție recursivă pentru generarea numărului de șiruri
   def count_sequences(current_element, current_count, current_index):
       if current_index == n:
           return 1
       total_sequences = 0
       for i in range(current_element, m + 1):
           if current_count + 1 <= k:
               total_sequences += count_sequences(i, current_count + 1, current_index + 1)
       total_sequences += count_sequences(current_element, 0, current_index + 1)
       return total_sequences
   return count_sequences(1, 0, 0)

if __name__ == "__main__":

   # Citim datele de intrare
   n, m, k = map(int, input().split())
   # Calculăm rezultatul și afișăm rezultatul
   rezultat = numar_siruri(n, m, k)
   print(rezultat)
</syntaxhighlight>