Fişierul intrare/ieşire:cmmp1.in, cmmp1.outSursăInfo-Oltenia 2019 clasele 5-6
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cmmp1 (clasele 7/8)

Notă: aceasta este problema cmmp cu limita de timp micşorată de la 1s la 0.15s. Este necesar să optimizaţi şi implementarea, nu doar algoritmul.

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].

Cerinţă

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

Date de intrare

Fişierul de intrare cmmp1.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 cmmp1.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

  • 1 ≤ N ≤ 105
  • 0 ≤ s[k] < 105
  • Pentru 20% din teste 0 ≤ s[k] < 102
  • Pentru 20% din teste 0 ≤ s[k] < 103
  • Dacă numărul dat este pătrat perfect, atunci operaţia „cmmp” îl lasă neschimbat
  • Mărimea maximă a sursei: 10KB

Exemplu

cmmp1.incmmp1.outExplicaţie
4
21 0 19 80
121 0 196 2809
121 = 112, 0 = 02, 196 = 142, 2809 = 532
Trebuie sa te autentifici pentru a trimite solutii. Click aici