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

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()