Vizualizare sursă pentru „2597 - PermutarePow”

== Cerința ==
Fie '''∆''' o permutare de gradul '''n'''. Se cere să se calculeze perioada principală a funcției '''f(x)''' = '''∆^x'''.
== Date de intrare ==
Fișierul de intrare '''permutarepowin.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale distincte separate prin spații, reprezentând valorile permutării '''∆'''.
== Date de ieșire ==
Fișierul de ieșire '''permutarepowout.txt''' va conține pe prima linie numărul '''P''', reprezentând perioada principală a funcției '''f'''.
== Restricții și precizări ==
* '''1 ≤ n ≤ 1.000.000'''
* Numerele de pe a doua linie vor aparține intervalului '''[1,n]'''
* Despre permutări
== Exemplul 1 ==
; permutarepowin.txt
: 4
: 3 4 2 1
; permutarepowout.txt
: Datele introduse corespund restricțiilor impuse.
: 4
== Explicație ==
Se observă că '''∆''' = '''∆^5''', deci perioada principală este '''4'''.
== Exemplul 2 ==
; permutarepowin.txt
: 5
: 1 2 3 4 6
; permutarepowout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 2597 - PermutarePow
import math


def validare(permutare_intrare):           # functia de validare a datelor de intrare
    n_intrare = len(permutare_intrare)
    if n_intrare < 1 or n_intrare > 1000000:
        raise ValueError

    for numar in permutare_intrare:
        if numar < 1 or numar > n_intrare:    # fiecare numar trebuie sa fie intre 1 si n
            raise ValueError

    fisier_iesire.write("Datele introduse corespund restrictiilor impuse.\n")


def perioada_principala(permutare_intrare):
    n_intrare = len(permutare_intrare)
    vizitat = [False] * n_intrare
    cicluri = []

    for i in range(n_intrare):
        if not vizitat[i]:
            ciclu = 0
            j = i
            while not vizitat[j]:
                vizitat[j] = True
                ciclu += 1
                j = permutare_intrare[j] - 1
            cicluri.append(ciclu)

    p_curent_local = cicluri[0]
    for i in range(1, len(cicluri)):
        p_curent_local = (p_curent_local * cicluri[i]) // math.gcd(p_curent_local, cicluri[i])

    return p_curent_local


if __name__ == '__main__':
    fisier_intrare = open("permutarepowin.txt", "r")
    fisier_iesire = open("permutarepowout.txt", "w")

    try:
        n = int(fisier_intrare.readline())
        permutare = list(map(int, fisier_intrare.readline().split()))

        validare(permutare)                 # apelul functiei de validare
        p_curent = perioada_principala(permutare)  # apelul functiei de rezolvare

        fisier_iesire.write(str(p_curent))

    except ValueError:
        fisier_iesire.write("Datele introduse nu corespund restrictiilor impuse.")

</syntaxhighlight>