Editing 0149 - Scara

Claudia vrea să construiască o scară cu <code>N</code> trepte astfel încât prima treaptă să fie la înălţimea <code>0</code> şi ultima treaptă să fie la înălţimea <code>H</code>. 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ă, <code>K</code>. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât <code>H</code>.

= Cerinţa =
Scrieţi un program care să determine numărul de scări diferite cu <code>N</code> 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 <code>666013</code>.

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

= Date de ieşire =
Fişierul de ieşire <code>scaraOUT.txt</code> va conţine pe prima linie o valoare care reprezintă numărul cerut. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

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

= Exemplu 1: =
<code>scaraIN.txt</code>
 4 3 2
<code>scaraOUT.txt</code>
 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: =
<code>scaraIN.txt</code>
 4 3 4
<code>scaraOUT.txt</code>
 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