# PBinfo #2934 – Cmmp – Rezolvare C++

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

## Enunț

Cerința
Pentru orice număr natural x definim operația cmmp prin care adăugăm cifre la stânga lui x, la dreapta lui x sau la ambele capete ale lui x, astfel încât numărul obținut să fie pătrat perfect și cât mai mic posibil.
 
Se dau N numere naturale \(  {s}_{1},{s}_{2}…{s}_{N} \).

Să se determine pentru fiecare număr s[k], 1 ≤ k ≤ N, cel mai mic pătrat perfect care se poate obține prin aplicarea operației cmmp.

Date de intrare
Fișierul de intrare cmmp.in conține pe primul rând numărul N. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu.

Date de ieșire
În fișierul de ieșire cmmp.out vor fi scrise, în ordinea corespunzătoare citirii și separate prin câte un spațiu, cele N numere obținute din numerele date prin aplicarea operației cmmp.

Restricții și precizări

1 ≤ N ≤ 100.000
0 ≤ s[k] < 100.000
Pentru 20% din teste 0 ≤ s[k] < 100
Pentru 20% din teste 0 ≤ s[k] < 1000
Dacă numărul dat este pătrat perfect, atunci operația cmmp îl lasă neschimbat.

Exemplu:
cmmp.in

4
21 0 19 80
cmmp.out

121 0 196 2809
Explicație
121 = 112, 0 = 02, 196 = 142, 2809 = 532

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("cmmp.in");
ofstream fout("cmmp.out");
unsigned long long i,j,k,pp,x,cif,nr,n,v[DIM],f[DIM];
int main() {
	for (i=1;pp<100000;i++) { //precalculam toate subsecventele de cifre care apar
		x=1LL*i*i;			  //in primele 100000 de patrate perfecte
		cif=0;
		while (x!=0) {
			v[++cif]=x%10;
			x/=10;
		}
		for (j=cif;j>0;j--) {
			nr=0; //in nr vom avea toate subsecventele de cifre ale lui x(i^2)
			for (k=j;k>=1&&j-k+1<=5;k--) {
				nr=nr*10+v[k];
				if (f[nr]==0) { //in f[nr] vom avea cel mai mic numar care
					f[nr]=i;	//ridicat la patrat il va contine pe nr
					pp++;
				}
			}
		}
	}
	f[0]=0; //din precalculare era 100
	fin>>n;
	for (i=1;i<=n;i++) {
		fin>>x;
		fout<<1LL*f[x]*f[x]<<" ";
	}
	return 0;
}
```

## Resurse

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