# PBinfo #1664 – Palindrom_Ciclic – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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_ciclic.in 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

Exemplu:
palindrom_ciclic.in

4
1 1 2 2
palindrom_ciclic.out

DA 1
Explicație
Șirul a devenit palindrom după o singură permutare la stânga , fiind în acest caz 1 2 2 1.

## Cod sursă C++

```cpp
//SUBIECTUL III: palindrom ciclic - solutia oficiala a facultatii ( modificata la citire , afisare si la declararea vectorului care era prea mic )
#include <fstream>
using namespace std ;
ifstream fin ("palindrom_ciclic.in") ;
ofstream fout ("palindrom_ciclic.out") ;
void citireSir(int &n, int a[]){
	fin >> n;
	for (int i = 0; i < n; i++){
		fin >> a[i];
	}
}
//verifica daca o secventa (a sirului a) care incepe pe pozitia start si
//se termina pe pozitia end este palindrom sau nu
bool estePalindrom(int a[], int start, int end){
	int i = start;
	int j = end;
	//se verifica perechi de elemente (cu indici simetrici fata de mijlocul secventei)
	//cand se gaseste o pereche de elemente diferite se opreste cautarea
	while ((a[i] == a[j]) && (i < j)){
		i++;
		j--;
	}
	//daca s-au verificat toate perechile si toate au avut elemente egale
	if (i >= j)
		return true;
	else
		return false;
}
//determina numarul de permutari ciclice care transforma un sir a cu n numere în palindrom
//daca sirul nu se poate transforma in palindrom prin permutari circulare, se returneaza -1
int numarPermutari(int n, int a[]){
	//se "dubleaza" sirul, copiind toate elementele inca o data in sir
	for (int i = 0; i < n; i++)
		a[n + i] = a[i];
	bool gasit = false;
	int i = 0;
	while ((i < n) && !gasit){
		//se verifica daca secventa care incepe pe pozitia i si are n elemente
		//este palindrom sau nu
		gasit = estePalindrom(a, i, i + n - 1);
		i++;
	}
	if (gasit)
		return i - 1;
	else
		return -1;
}
//in cazul unui numar (primit ca parametru) pozitiv, afiseaza mesajul "da" si
//valoarea numarului
//in cazul unui numar (primit ca parametru) negativ, afiseaza mesajul "nu"
void afisare(int nr){
	if (nr >= 0)
		fout << "DA " << nr ;
	else
		fout << "NU" ;
}
//Program principal
int main()
{
	int nrElemente = 0;
	int sir[2001];
	citireSir(nrElemente, sir);
	int nrPerm = numarPermutari(nrElemente, sir);
	afisare(nrPerm);
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1664)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1664/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1664/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)