3821 - Magic Digits

Cerința

Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca fiind suma dintre frecvența minima a unei cifre magice și frecvența maxima a unei cifre magice care se găsește în număr. Formal , dacă construim un vector f , unde f[i] este numărul de apariții ale cifrei i și se șterg toate valorile pentru care f[i] = 0 , atunci min(f) + max(f) = k , unde k este gradul de frumusețe al numărului. De exemplu , pentru numărul 131 gradul de frumusețe este 1+2 = 3. Le Quack își pune următoarea întrebare : Câte numere de n cifre au gradul de frumusețe egal cu k ?

Date de intrare

Programul citește de la tastatură pe prima linie un număr N reprezentând lungimea numerelor care trebuie numărate și k , gradul de frumusețe al lor.

Date de ieșire

Programul va afișa pe ecran numărul cerut modulo 666013.

Restricții și precizări

N <= 300. K <= 2*N. Pentru 10 puncte N <= 6. Pentru alte 10 puncte , K > N. Pentru restul de 80 de puncte , K <= N , N > 6 si N <= 300. Nu uitați că cifra 0 nu poate fi folosită ! ==Exemplu==: Intrare

2 2 Ieșire

72 Intrare

3 2 Ieșire

504

Explicație

În primul exemplu , sunt 72 de numere de lungime 2 cu gradul de frumusețe 2. câteva dintre acestea sunt : 13 , 14 , 32. În al doilea exemplu sunt 504 numere de lungime 3 cu gradul de frumusețe 2. Câteva dintre acestea sunt : 132 , 152 , 512.

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 666013

def numere_grad_frumusete(N, k):

  # Funcție auxiliară pentru calculul coeficientului binomial
  def comb(n, r):
      result = 1
      for i in range(r):
          result = (result * (n - i)) % MOD
          result = (result * pow(i + 1, MOD - 2, MOD)) % MOD
      return result
  # Funcție recursivă pentru generarea numărului de aranjamente
  def count_arrangements(digit_counts, current_k):
      if current_k < 0:
          return 0
      if current_k == 0:
          # Calculăm numărul de moduri în care putem aranja cifrele
          result = 1
          for count in digit_counts:
              result = (result * comb(N, count)) % MOD
          return result
      total_arrangements = 0
      for i in range(1, 10):
          # Adăugăm cifra i și continuăm recursiv
          new_digit_counts = digit_counts[:]
          new_digit_counts.append(i)
          total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD
      return total_arrangements
  return count_arrangements([], k)

if __name__ == "__main__":

  # Citim datele de intrare
  N, k = map(int, input().split())
  # Calculăm rezultatul și afișăm rezultatul modulo MOD
  rezultat = numere_grad_frumusete(N, k)
  print(rezultat)

</syntaxhighlight>