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
Constanta_mod = 666013
# Constanta pentru operatia modulo
numar_n = 0
# Definim functie pentru inmultirea matricei
def inmultire_matrice(numar_a, numar_b):
raspuns = [[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):
raspuns[i][j] += numar_a[i][k] * numar_b[k][j]
if numar_n > 1000:
# Aplicam operatia modulo daca n > 1000
raspuns[i][j] %= Constanta_mod
return raspuns
def main():
# Deschidem fisierele input si output
fin = open("veverita4.in", "r")
fout = open("veverita4.out", "w")
# Citim valoarea numarului "n" din fisierul input
numar_n = int(fin.readline())
# Definim matricea initiala "matrice"
matrice = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]
# Initializam rezultatul matricei "matrice_rezultata" ca matrice de identitate
matrice_rezultata = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
# Efectuam exponentierea matricei folosind metoda exponentierei binare
exponent = numar_n - 1
while exponent:
if exponent % 2 == 1:
# Inmultim matricea_rezultata cu matricea
matrice_rezultata = inmultire_matrice(matrice_rezultata, matrice)
# Ridicam matricea la puterea 2
matrice = inmultire_matrice(matrice, matrice)
exponent = int(exponent / 2)
# Calculam rezultatul final apeland elementele din "matrice_rezultata"
raspuns = 0
for i in range(4):
for j in range(4):
raspuns += matrice_rezultata[i][j]
# Aplicam operatia modulo daca n > 1000
if numar_n > 1000:
raspuns %= Constanta_mod
# Scriem rezultatul final in fisierul output si inchidem fisierele
fout.write(str(raspuns))
fin.close()
fout.close()
# Verificam daca scriptul este rulat direct
if __name__ == "__main__":
# Apelam functia main()
main()
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