Etichete : .campion, algoritmica, informatica, OJI, ONI, palc, Probleme algoritmica

Un şir de caractere se numeşte palindrom dacă se citeşte la fel de le stânga la dreapta şi de la dreapta la stânga, de exemplu “capac”, “12321″.

Şirul se va numi palindrom ciclic dacă se transformă în palindrom prin o serie de permutări ciclice a elementelor sale. O permutare ciclică a elementelor şirului de caractere este deplasarea lor cu o poziţie spre stânga (în acest caz primul element trece în ultima poziţie) sau spre dreapta (ultimul element trece în prima poziţie) De exemplu, AABB se transformă în ABBA prin o singură permutare ciclică la stânga; 345432112 – prin două permutări ciclice la dreapta (23453211; 123454321) sau prin şapte permutări (454321123; 543211234; 432112345; 321123454; 211234543; 112345432; 123454321).

Cerinţă

Scrieţi un program, care să determine dacă un şir dat de caractere este un palindrom ciclic sau nu, precum şi numărul minim de permutări ciclice ale şirului de caractere, care îl transformă în palindrom.

Date de intrare

Fişierul de intrare palc.in va conţine o singură linie pe care va fi scris şirul de caractere S.

Date de ieşire

Fişierul text palc.out va conţine o singură linie pe care va fi scris un singur număr întreg: -1, dacă şirul de caractere S nu poate fi transformat în palindrom prin permutări ciclice, respectiv numărul minim de permutări ciclice care transformă şirul de caractere S în palindrom.

Restricţii

• Lungimea şirului de caractere S < = 200
• Şirul de caractere S poate conţine numai litere, cifre şi spaţii.

Exemple

Solutie Oficiala

Se vor realiza cel mult k/2 permutari ciclice spre stanga si spre dreapta. La fiecare permutare se verifica daca cel puţin unul dintre sirurile obţinute este palindrom. Daca in nici una din directii nu s-a obtinut palindromul prin k/2 permutari rezultatul este -1. Altfel se inscrie indicele transformarii care genereaza palindromul.

Solutia mea(mai interesanta si mai detaliata)

Solutia de mai sus mi s-a parut putin cam neinteresanta din punctul de vedere al lucrurilor noi invatate.Metoda pe care am abordat-o eu a fost dublarea sirului de caractere si incepand de la i=0 pana la n(lungimea sirului initial) am verificat daca avem un palindrom.Solutia este MIN(i,n-i).

Descarcati solutia la problema palc,Campion 2009 – runda 4

Recomandam, pe aceeasi tema

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 591 articole (vezi lista completa).

Contact | andrei@worldit.info | @worldIT – @AndreiAvadanei

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.