Editing 4287 - Veverita 4


În parcul orașului există <code>4</code> rânduri de câte <code>n</code> copaci perfect aliniați. Rândurile sunt notate A, B, C și D, iar copacii de pe fiecare rând sunt numerotați de la <code>1</code> la <code>n</code>, ca în imaginea de mai jos:


O veveriță jucăușă sare prin copaci astfel:

* pornește dintr-un copac numerotat cu <code>1</code>;
* la fiecare pas sare dintr-un copac numerotat cu <code>i</code> într-un copac numerotat cu <code>i+1</code>. Dacă se află într-un copac de pe rândul A, va sări în copacul de pe rândul B, dacă se află într-un copac de pe rândul D, va sări în copacul de pe rândul C, dacă se află în copacul de pe rândul B, va sări în copacul de pe rândul A sau în copacul de pe rândul C, iar dacă se află în copacul de pe rândul C, va sări în copacul de pe rândul B sau în copacul de pe rândul D;
* se oprește într-unul dintre copacii numerotați cu <code>n</code>.

= Cerința =
<syntaxhighlight lang="python3">
MOD = 666013     #definim constanta pentru operatia modulo

fin = open("veverita4.in", "r")   #deschidem fisierele input si output
fout = open("veverita4.out", "w")

n = int(fin.readline())              #citim valoarea lui "n" din fisierul input

#definim functie pentru inmultirea matricei
def mat_multiply(a, b)
    ans = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans[i][j] += a[i][k] * b[k][j]
            if n > 1000:#aplicam operatia modulo daca n>1000
                ans[i][j] %= MOD
    return ans                      # ridicam matricea la puterea n-1

#definim matricea initiala "mat"
mat = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]
#initializam rezultatul matricel "ansmat" ca matrice de identitate
ansmat = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
#efectuam exponentierea matricei folosind metoda exponentierei binare
exp = n - 1
while exp:
    if exp % 2 == 1:
        ansmat = mat_multiply(ansmat, mat)
    mat = mat_multiply(mat, mat)
    exp = int(exp / 2)
    #calculam rezultatul final apeland elementele din "ansmat"
ans = 0
for i in range(4):
    for j in range(4):
        ans += ansmat[i][j]
#aplicam operatia modulo daca n>1000
if n > 1000:
    ans %= MOD
#scriem rezultatul final in fisierul output si inchidem fisierul
fout.write(str(ans))
fin.close()
fout.close()
</syntaxhighlight>Aflați numărul <code>M</code> de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă <code>n</code> este mai mic sau egal cu <code>1000</code>, atunci veți afișa chiar numărul <code>M</code>, iar dacă <code>n</code> este mai mare decât <code>1000</code>, veți afișa restul împărțirii lui <code>M</code> la <code>666013</code>.

= Date de intrare =
Fișierul de intrare <code>veverita4.in</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>veverita4.out</code> va conține pe prima linie valoarea cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 109</code>
* pentru 60% din teste, <code>n ≤ 1000</code>;
* pentru alte 40% din teste, <code>n ≤ 109</code>;

= Exemplu =
<code>veverita4.in</code>
 3
<code>veverita4.out</code>
 10