# PBinfo #4463 – pcp – Rezolvare C++

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

## Enunț

Se consideră un număr natural nenul N.

Cerința
Să se determine toate pătratele perfecte distincte care se obțin prin permutarea cifrelor numărului N. Exemple:


Pentru N = 691 prin permutarea cifrelor sale se obțin numerele 169, 196, 619, 691, 916, 961 din care 3 sunt pătrate perfecte: 169 = 132, 196 = 142 și 961 = 312.
Pentru N = 1044 prin permutarea cifrelor sale se obțin numerele 0144, 0414, 0441, 1044, 1404, 1440, 4014, 4041, 4104, 4140, 4401, 4410 din care 2 sunt pătrate perfecte: 144 = 122, 441 = 212.

Date de intrare
Fișierul de intrare pcp.in conține pe primul rând numărul natural N.

Date de ieșire
Fișierul de ieșire pcp.out va conține pe prima linie numărul P reprezentând numărul de pătrate perfecte care se pot obține prin permutarea cifrelor numărului N și apoi pe următoarele P linii cele P pătrate perfecte în ordine crescătoare. Dacă nu există niciun pătrat perfect ce se poate obține prin permutarea cifrelor lui N se va afișa mesajul nu exista. 

Restricții și precizări

0 < N < 1014
Cifrele de 0 care prin permutarea cifrelor lui N apar la începutul unui număr, nu se iau în considerare.
Pentru 20 de puncte, 1 ≤ N < 10.000
Pentru 68 de puncte, 104 ≤ N < 1013
Pentru 12 de puncte, 1013 ≤ N < 1014

Exemplul 1:
pcp.in

691
pcp.out

3
169
196
961
Exemplul 2:
pcp.in

1044
pcp.out

2
144
441
Exemplul 3:
pcp.in

202050
pcp.out

4
225
2025
22500
202500
Exemplul 4:
pcp.in

2023
pcp.out

nu exista

## Cod sursă C++

```cpp
#include <fstream>
#include <algorithm>
#include <math.h>
using namespace std;
ifstream f("pcp.in");
ofstream g("pcp.out");
long long n,m,pp,x,i,j,a,ok,sol,r,u,b[100000],a1,m1,rest,pas;
int v[10],w[10],z[10];
void calcul()
{
    for(i = a1; i <= a; i = i+pas)
    {
        for(u = 0; u <= 9; u++)
            w[u] = 0;
        x = i*i;
        pp = x;
        while(x != 0)
        {
            r = x%10;
            w[r]++;
            x = x/10;
        }
        ok = 1;
        for(u = 1; u <= 9; u++)
            if(w[u]!=v[u]) ok = 0;
        if(w[0]>v[0]) ok = 0;
        if(ok==1)
        {
            sol++;
            b[sol] = pp;
        }
    }
}
int main()
{
    f >> n;
    while(n!=0)
    {
        r = n%10;
        v[r]++;
        w[r]++;
        z[r]++;
        rest += r;
        n = n/10;
    }
    rest = rest%9;
    m = 0;
    for(i = 9; i >= 0; i--)
        while(w[i]>0)
        {
            m = m*10+i;
            w[i]--;
        }
    m1 = 0;
    for(i = 1; i <= 9; i++)
        while(z[i]>0)
        {
            m1 = m1*10+i;
            z[i]--;
        }
    a = floor(sqrt(m));
    a1 = floor(sqrt(m1));
    sol = 0;
    if(rest==0)
    {
        if(a1%3!=0)
            a1 = a1+(3-a1%3);
        pas = 3;
        calcul();
    }
    else
    if(rest==4)
    {
        if(a1%9==2)
        {
            pas = 9;
            calcul();
            a1 += 5;
            calcul();
        }
        else
        if(a1%9==7)
        {
            pas = 9;
            calcul();
            a1 += 4;
            calcul();
        }
        else
        {
            if(a1%9 < 2)
            {
                a1 += 2-a1%9;
                pas = 9;
                calcul();
                a1 += 5;
                calcul();
            }
            else
            if(a1%9 < 7)
            {
                a1 += 7-a1%9;
                pas = 9;
                calcul();
                a1 += 4;
                calcul();
            }
            else
            {
                a1 += 3;
                pas = 9;
                calcul();
                a1 += 5;
                calcul();
            }
        }
    }
    else
    if(rest==7)
    {
         if(a1%9==4)
        {
            pas = 9;
            calcul();
            a1++;
            calcul();
        }
        else
        if(a1%9==5)
        {
            pas = 9;
            calcul();
            a1 += 8;
            calcul();
        }
        else
        {
            while(a1%9!=4)a1++;
            pas = 9;
            calcul();
            a1++;
            calcul();
        }
    }
    else
    {
       if(a1%9==0)
       {
           a1++;
           pas = 9;
           calcul();
           a1 += 7;
           calcul();
       }
       else
       if(a1%9==1)
       {
           pas = 9;
           calcul();
           a1 += 7;
           calcul();
       }
       else
       if(a1%9 < 8)
       {
           a1 += 8-a1%9;
           pas = 9;
           calcul();
           a1 += 2;
           calcul();
       }
       else
       {
           pas = 9;
           calcul();
           a1 += 2;
           calcul();
       }
    }
    if(sol==0) g << "nu exista\n";
    else{
    sort(b+1,b+sol+1);
    g << sol << "\n";
    for(i = 1; i <= sol; i++)
        g << b[i] << "\n";
    }
    return 0;
}
```

## Resurse

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