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">

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>