1664 - Palindrom Ciclic

Cerința

Un șir de numere naturale se numește palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga. De exemplu, șirul (1, 2, 3, 2, 1) este palindrom, iar șirul (1, 2, 3, 2, 4) nu este palindrom. Un șir de numere naturale se numește palindrom ciclic dacă se transformă în palindrom printr-o serie de permutări ciclice ale elementelor sale. O permutare ciclică a elementelor șirului reprezintă deplasarea lor cu o poziție spre stânga (cu excepția primului element, care trece pe ultima poziție).

Scrieţi un program care decide dacă un șir a , având n elemente numere naturale este un palindrom ciclic sau nu . În caz afirmativ, programul va determina numărul de permutări ciclice care transformă șirul dat în palindrom.

Se recomandă definirea și apelarea de subprograme pentru :

- citirea șirului din fișier ;

- afișarea mesajului corespunzător ;

- verificarea proprietății de palindrom ;

- determinarea numărului de permutări necesare .

Date de intrare

Fișierul de intrare palindrom_ciclicIN.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații , reprezentând șirul care trebuie verificat .

Date de ieșire

Fișierul de ieșire palindrom_ciclic.out va conține pe prima linie un mesaj : DA , respectiv NU . În caz afirmativ , se va mai afișa un număr despărțit de mesaj printr-un spațiu care va reprezenta numărul ( minim ) de permutări necesare șirului să devină palindrom .

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• În această problemă , permutările se fac doar spre stânga

Exemplul 1

palindrom_ciclicIN.txt:

4

1 1 2 2

palindrom_ciclicOUT.txt

DA 1

Exemplul 2

palindrom_ciclicIN.txt:

1001

1 1 2 2 323 23 23232 1 1 11 1 11 1 1

Output consola: Dimensiunea n trebuie să fie în intervalul [1, 1000].

Rezolvare

<syntaxhighlight lang="python3" line="1"> def citeste_sir_din_fisier(numefisier):

   with open(numefisier, "r") as f:
       n = int(f.readline())
       sir = list(map(int, f.readline().split()))
   return n, sir

def scrie_output_in_fisier(numefisier, palindrom_ciclic, num_permutari):

   with open(numefisier, "w") as f:
       if palindrom_ciclic:
           f.write(f"DA {num_permutari}\n")
       else:
           f.write("NU\n")

def este_palindrom_ciclic(sir):

   n = len(sir)
   for i in range(1, n + 1):
       permutare = sir[i:] + sir[:i]
       if sir == permutare[::-1]:
           return i - 1  # Ajustare pentru a afișa numărul corect de permutări ciclice
   return 0

def verifica_criterii(n, sir):

   if n < 1 or n > 1000:
       print("Dimensiunea n trebuie să fie în intervalul [1, 1000].")
       return False, 0

   if any(x <= 0 or x >= 1000000000 for x in sir):
       print("Numerele trebuie să fie mai mici decât 1.000.000.000.")
       return False, 0

   return True, 0

def main():

   numefisier = "palindrom_ciclicIN.txt"  # numele fișierului de intrare și output
   fisierout = "palindrom_ciclicOUT.txt"  # nume fișier output

   n, sir = citeste_sir_din_fisier(numefisier)

   criterii_valide, _ = verifica_criterii(n, sir)
   if not criterii_valide:
       return

   palindrom_ciclic = este_palindrom_ciclic(sir)

   scrie_output_in_fisier(fisierout, palindrom_ciclic, palindrom_ciclic)

if __name__ == "__main__":

   main()

</syntaxhighlight>