2934 - Cmmp

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 s1,s2…sN .

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 1

Intrare

4
21 0 19 80

Iesire

121 0 196 2809

Rezolvare

<syntaxhighlight lang="python" line> import math

def is_perfect_square(x):

   """Verifică dacă un număr este pătrat perfect."""
   s = int(math.isqrt(x))
   return s * s == x

def cmmp_operation(x):

   """Aplică operația cmmp pentru a obține cel mai mic pătrat perfect."""
   if is_perfect_square(x):
       return x
   
   x_str = str(x)
   min_perfect_square = float('inf')
   
   for i in range(10):
       for j in range(10):
           for k in range(10):
               possible_numbers = [
                   int(str(i) + x_str),
                   int(x_str + str(j)),
                   int(str(i) + x_str + str(j)),
                   int(str(k) + str(i) + x_str + str(j)),
               ]
               for num in possible_numbers:
                   if is_perfect_square(num):
                       min_perfect_square = min(min_perfect_square, num)
   
   return min_perfect_square if min_perfect_square != float('inf') else x

def main():

   with open('cmmp.in', 'r') as f:
       data = f.read().splitlines()

   N = int(data[0].strip())
   numbers = list(map(int, data[1].strip().split()))
   
   assert 1 <= N <= 100000, "N trebuie să fie între 1 și 100000"
   assert all(0 <= x <= 100000 for x in numbers), "Numerele trebuie să fie între 0 și 100000"

   results = [cmmp_operation(num) for num in numbers]

   with open('cmmp.out', 'w') as f:
       f.write(' '.join(map(str, results)) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>