# PBinfo #3764 – cat2pal – Rezolvare C++

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

## Enunț

Prin concatenarea a două numere naturale A și B se pot obține numerele naturale AB și BA. De exemplu, dacă A = 8 și B = 8, atunci prin concatenare se poate obține numărul 88, iar dacă A = 7 și B = 17, atunci prin concatenare se pot obține numerele 717 și respectiv 177.

Cerința
Scrieți un program care să rezolve următoarele două cerințe:

1. Pentru un număr natural nenul A dat, să se calculeze P1, numărul numerelor naturale distincte X, unde 1 ≤ X ≤ 10 * A, astfel încât X concatenat cu A sau A concatenat cu X este palindrom.
2. Date fiind numărul natural N și un șir de N numere naturale v[1], v[2], …, v[N], să se calculeze P2, numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile (v[i], v[j]), unde 1 ≤ i ≤ N și 1 ≤ j ≤ N.

Date de intrare
Fișierul de intrare cat2pal.in conține pe prima linie numărul natural C, reprezentând cerința care urmează să fie rezolvată (1 sau 2). Dacă C = 1, atunci pe linia a doua se află numărul natural A. Dacă C = 2, atunci pe linia a doua se află numărul natural N și pe linia a treia se află N numere naturale separate prin spațiu, reprezentând șirul v.

Date de ieșire
Fișierul de ieșire cat2pal.out va conține o singură linie pe care se va scrie un singur număr natural, reprezentând rezultatul pentru cerința C din fișierul de intrare.

Restricții și precizări

1 ≤ A < 100.000.000
1 ≤ N ≤ 10.000
0 ≤ v[i] < 100.000; pentru orice i = 1..N
Pentru cazul C = 2, trebuie luate în considerare și perechile (v[i], v[i]), adică concatenarea unui element cu el însuși.

Exemplul 1:
cat2pal.in

1
2
cat2pal.out

3
Explicație
C = 1, A = 2, numerele X care concatenate cu A produc numere palindrom sunt 2, 12 și 20, deci P1 = 3.

Exemplul 2:
cat2pal.in

2
3
2 12 21
cat2pal.out

4
Explicație
C = 2, N = 3, v = {2, 12, 21}, numerele palindrom distincte care pot fi obținute sunt 22, 212, 1221, 2112, deci P2 = 4.

## Cod sursă C++

```cpp
///Complexitate O(log(A)) pentru cerinta 1
///Complexitate O(N*sigma*sigma)
#include <fstream>
using namespace std;
ifstream  fin("cat2pal.in");
ofstream fout("cat2pal.out");
int N,v[10002], nw, c, ok, i, j, k, C , P1, P2;
long long z, s, t, w[100], s1, s2, t1, t2, x1, x2, x, y, r, X, A, vi, vj, p, q, d;
char f[100002], f0[100002], f1[100002];
int main(){fin>>C;
    if(C==1){fin>>A;
      ///voi adauga in w[] toate solutiile posibile, apoi sortez si apoi verific
      ///solutiile posibile sunt printre prefixele sau sufixele oglinditului lui A
      ///eventual precedate sau succedate de una dintre cifrele 0,1,...,9
      x=A; while(x%10==0){x=x/10;};///tai zerourile de la final
      p=1;y=0;do{y=y*10+x%10;x=x/10;p=p*10;}while(x>0);///y=oglindit(A)
      ///adaug sufixele si prefixele lui y
      nw=0; q=p; r=y;
      do{ w[++nw]=y%q; w[++nw]=r;
        q=q/10; r=r/10;
      }while(r);
      ///lipesc cate o cifra la stanga si la dreapta lui y si adaug in w[]
        for(c=0;c<=9;c++){
            d=y*10+c; if(d<=A*10){w[++nw]=d;}
            d=c*p+y; if(d<=A*10){w[++nw]=d;}
        }
      ///sortez candidatii
      for(i=1;i<=nw-1;i++)
        for(j=i+1;j<=nw;j++)
            if(w[i]>w[j]){ int aux=w[i]; w[i]=w[j]; w[j]=aux; }
      ///verific si selectez doar solutiile
      w[0]=0;P1=0;
      q=1;while(q<=A){q=q*10;}
      for(i=1;i<=nw;i++)
        if(w[P1]!=w[i]){///verific daca w[i] este o solutie
          p=1;while(p<=w[i]){p=p*10;}
          s1=0; x1=A*p+w[i]; t1=x1; do{s1=s1*10+t1%10;t1=t1/10;}while(t1);
          s2=0; x2=w[i]*q+A; t2=x2; do{s2=s2*10+t2%10;t2=t2/10;}while(t2);
          if(s1==x1 ||s2==x2){///DA, w[i] este solutie
            w[++P1]=w[i];
          }
        }
      fout<<P1<<"\n";
    }
    if(C==2){ fin>>N;
      for(i=1;i<=N;i++){ fin>>v[i]; f[v[i]]=1; }
    ///f[x]=1 daca x este din v[]
    ///orice palindrom de lungime j se poate identifica prin sufix de lungime j-j/2
    ///f0[x]=1 daca x este sufix de palindrom de lungime para
    ///f1[x]=1 daca x este sufix de palindrom de lungime impara
      ///oglinditele prefixelor
      for(i=1;i<=N;i++){
        vi=v[i]; while(vi && vi%10==0){vi=vi/10;}
        p=1; y=0; do{y=y*10+vi%10;vi/=10;p=p*10;}while(vi);
        do{
          if(y*10>=p && f[y]==1){///daca y este element din v[]
            z=p*v[i]+y;
            s=z; t=0; j=0; do{j++; t=t*10+s%10;s=s/10;}while(s);
            if(z==t){///si lipit la dreapta lui v[i] avem palindrom
              ///construim in s sufixul identificator pentru z
              k=j-j/2; s=0; while(k){s=s*10+t%10;t=t/10;k--;}
              if(j%2==0){f0[s]=1;}
              else{f1[s]=1;}
            }
          }
          p=p/10;y=y%p;
        }while(p>=10);
      }
      ///oglinditele sufixelor
      for(i=1;i<=N;i++){
        vi=v[i]; p=1; y=0; do{y=y*10+vi%10;vi=vi/10;p=p*10;}while(vi);
        do{
          if(f[y]==1){///daca este din v[]
            z=y*p+v[i];///lipim in stanga lui v[i]
            s=z; t=0; j=0; do{j++; t=t*10+s%10;s=s/10;}while(s);
            if(z==t && f[y]==1){///este palindrom
              ///construim in s sufixul identificator pentru z
              k=j-j/2; s=0; while(k){s=s*10+t%10;t=t/10;k--;}
              if(j%2==0){f0[s]=1;}
              else{f1[s]=1;}
            }
          }
          y=y/10;
        }while(y>0);
      }
      P2=0;
      for(i=0;i<100000;i++){P2=P2+f0[i]+f1[i];}
      fout<<P2<<"\n";
    }
    fout.close(); fin.close();
    return 0;
}
```

## Resurse

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