2114A - A. Square Year
-
Límite de tiempo por prueba: 1 segundo.
-
Límite de memoria por prueba: 256 megabytes.
-
Fecha: 16/09/2025.
-
Dificultad: 🍰 (800)
-
Tags: binary search, brute force, math
Se puede notar el siguiente hecho matemático notable: el número puede representarse como .
Se te da un año representado por una cadena , que consta exactamente de 4 caracteres. Por lo tanto, se permiten ceros a la izquierda en la representación del año. Por ejemplo, , y son representaciones válidas de años.
Necesitas expresarlo en la forma , donde y son enteros no negativos, o determinar que es imposible.
Por ejemplo, si , puedes elegir , , y escribir el año como .
Entrada
La primera línea de la entrada contiene un solo entero ( ): el número de casos de prueba.
Las líneas siguientes describen los casos de prueba.
La única línea de cada caso de prueba contiene una cadena , que consta de exactamente 4 caracteres. Cada carácter es un dígito del al .
Salida
En una línea separada para cada caso de prueba, imprime:
-
Dos números y ( ) tales que , si existen.
-
Si hay múltiples pares adecuados, puedes imprimir cualquiera de ellos. de lo contrario.
Ejemplo
| Input | Output |
|---|---|
|
|
Solución O(1) en Python
Para esta solución utilizando matemáticas (Estilo Ruso) simplemente debemos despejar los valores de y para que se cumpla la ecuación .
El ejercicio nos pide cualquier tipo de suma de valores, simplemente debe haber un par números que cumplan la ecuación. Si asumimos que el valor de simplificamos la ecuación a
.
Entonces podemos obtener el valor de con:
.
Esto nos permitirá saber el valor de , pero estamos trabajando solo con números enteros, por lo que se pierde precisión si la raíz del año es un número con decimales. Estos nos obliga a verificar el valor de y que deba ser igual al año si lo elevamos al cuadrado.
Es decir se debe cumplir lo siguiente: .
Una vez obtenidos estos valores, solamente queda mostrar el par y si no se encuentra un valor de que cumpla la restricción.
# python3 solution-o(1).py
import math
t = int(input())
for _ in range(0, t):
year = int(input())
b = int(math.sqrt(year))
if (math.pow(b, 2) == year):
print(0, b)
else:
print(-1)