4287 - Veverita 4

Î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 cu i+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

<syntaxhighlight lang="python3"> Constanta_mod = 666013

1. Constanta pentru operatia modulo

numar_n = 0

1. 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()

</syntaxhighlight>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