Editing 4287 - Veverita 4 (section)

= Cerința =
<syntaxhighlight lang="python3">
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()
</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>.