4287 - Veverita 4
De la Universitas MediaWiki
În parcul orașului există 4
rânduri de câte n
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 1
la n
, ca în imaginea de mai jos:
O veveriță jucăușă sare prin copaci astfel:
- pornește dintr-un copac numerotat cu
1
; - la fiecare pas sare dintr-un copac numerotat cu
i
într-un copac numerotat cui+1
. 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
n
.
Cerința
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()
Aflați numărul M
de modalități în care se poate deplasa veverița, respectând regulile de mai sus. Dacă n
este mai mic sau egal cu 1000
, atunci veți afișa chiar numărul M
, iar dacă n
este mai mare decât 1000
, veți afișa restul împărțirii lui M
la 666013
.
Date de intrare
Fișierul de intrare veverita4.in
conține pe prima linie numărul n
.
Date de ieșire
Fișierul de ieșire veverita4.out
va conține pe prima linie valoarea cerută.
Restricții și precizări
1 ≤ n ≤ 109
- pentru 60% din teste,
n ≤ 1000
; - pentru alte 40% din teste,
n ≤ 109
;
Exemplu
veverita4.in
3
veverita4.out
10