0149 - Scara

Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricare două trepte consecutive trebuie să fie mai mică sau egală cu o valoare dată, K. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât H.

Cerinţa

Scrieţi un program care să determine numărul de scări diferite cu N trepte, ce pot fi construite respectând cerinţele Claudiei. Deoarece numărul de scări poate fi foarte mare, determinaţi restul împărţirii acestui număr la 666013.

Date de intrare

Pe prima linie a fişierului scaraIN.txt se află numerele naturale N H K, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire scaraOUT.txt va conţine pe prima linie o valoare care reprezintă numărul cerut.

Restricţii şi precizări

• 1 ≤ N ≤ 109
• 1 ≤ H ≤ 100
• 1 ≤ K ≤ H
• Pentru un număr de teste în valoare de 30 de puncte, N ≤ 20.000 şi H ≤ 20
• Pentru un număr de teste în valoare de 50 de puncte, N ≤ 500.000 şi H ≤ 30
• Pentru un număr de teste în valoare de 80 de puncte, H ≤ 30

Exemplu 1:

scaraIN.txt

4 3 2

scaraOUT.txt

8

Explicație

0 0 1 3

0 2 3 3

0 1 2 3

0 1 3 3

0 2 1 3

0 0 2 3

0 1 1 3

0 2 2 3

Exemplu 2:

scaraIN.txt

4 3 4

scaraOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1"> HMAX = 105 MOD = 666013

def mul(A, B, h):

   C = [[0] * HMAX for _ in range(HMAX)]
   for i in range(h + 1):
       for j in range(h + 1):
           sum = 0
           for k in range(h + 1):
               sum += A[i][k] * B[k][j]
           C[i][j] = sum % MOD
   for i in range(h + 1):
       for j in range(h + 1):
           A[i][j] = C[i][j]

def main():

   with open("scaraIN.txt", "r") as infile:
       n, h, k = map(int, infile.readline().strip().split())
   
   if not (1 <= n <= 10**9) or not (1 <= h <= 100) or not (1 <= k <= h):
       with open("scaraOUT.txt", "w") as outfile:
           outfile.write("Datele nu corespund restrictiilor impuse\n")
       return
   
   A = [[0] * HMAX for _ in range(HMAX)]
   P = [[0] * HMAX for _ in range(HMAX)]
   
   for j in range(h + 1):
       A[j][j] = 1
       for i in range(h + 1):
           if j - k <= i <= j + k:
               P[i][j] = 1
   
   n -= 1
   while n:
       if n & 1:
           mul(A, P, h)
       mul(P, P, h)
       n >>= 1
   
   with open("scaraOUT.txt", "w") as outfile:
       outfile.write(f"{A[0][h]}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

0 0 1 3 0 2 3 3 0 1 2 3 0 1 3 3 0 2 1 3 0 0 2 3 0 1 1 3 0 2 2 3