Cuádruple#11854

Cuádruple (Editorial)

Autor del problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución 1 (Análisis Amortizado)

Consideremos un algoritmo ingenuo para el código, que consiste en iterar todos los $4$ enteros $(a, b, c, d)$ (a,b,c,d) con un límite superior $n$ tal que $b \geq a + 1$ b \ge a+1, $c \geq b + 1$ c \ge b+1, $d \geq c + 1$ d \ge c+1, y que no sean divisibles por $4$ y tengan una suma de $n$ .

Por supuesto, en teoría esto es $O (n^{4})$ \mathcal{O}(n^4). ¿Podemos optimizar? Sí, podemos eliminar $d$ , porque

a + b + c + d = n ⟹ d = n - (a + b + c)

\displaystyle a+b+c+d=n \implies d=n-(a+b+c)

Ahora tenemos un código de $O (n^{3})$ \mathcal{O}(n^3). ¿Y ahora qué? Solo envíalo, sí, el código es lo suficientemente eficiente y de hecho es $O (1)$ .

Prueba:

Observa que $(n \leq 10)$ (n \le 10) no tiene cuádruples válidos, así que solo imprime $- 1$ .

De lo contrario, considera la primera iteración de $(a, b, c) = (1, 2, 3)$ (a,b,c)=(1,2,3), no haremos más iteraciones mientras $(n - a - b - c) mod 4 \neq = 0$ (n-a-b-c) \bmod 4 \neq 0 porque satisface todas las condiciones, así que para el caso de $(n - (a + b + c)) mod 4 \neq = 0$ (n-(a+b+c)) \bmod 4 \neq 0 en realidad hacemos una sola iteración, lo que significa que para $n mod 4 \neq = 2$ n \bmod 4 \neq 2 haremos una sola iteración.

¿Qué pasa cuando $(n - (a + b + c)) mod 4 = 0$ (n-(a+b+c)) \bmod 4 =0? Te moverás a $a = 2, b = 3, c = 5$ a=2,b=3,c=5 y tendrás $d = n - 10$ d=n-10, $d mod 4 = 2$ d \bmod 4=2 lo cual es válido, así que solo harás $3$ iteraciones (ya que omitimos $c = 4$ c=4).

Complejidad $O (1)$

def solve():
    n=int(input())
    if(n<=10):
        print(-1)
    else:
        for a in range(1,n):
            for b in range(a+1,n):
                for c in range(b+1,n):
                    if(len(set([a,b,c,n-(a+b+c)]))==4 and a%4!=0 and b%4!=0 and c%4!=0 and (n-(a+b+c))%4!=0 and n-a-b-c>0):
                        print(a,b,c,n-a-b-c)
                        return
for _ in range(int(input())):
    solve()

Python

Complejidad $O (1)$

Solución 2 (Trabajo por Casos) Puedes decidir simplemente trabajar por casos en el código, claro, tenemos $2$ casos:

Caso 1: $(1 \leq n \leq 10)$ (1 \le n \le 10):

Este caso no tiene soluciones, así que solo imprime $- 1$ .

Lee la Solución del Análisis Amortizado para entender el punto de trabajar por casos aquí.

Caso 2: $n mod 4 \neq = 2$ n \bmod 4 \neq 2

Hay $4$ construcciones que al menos una de ellas debe cumplirse, hay

⎩ ⎨ ⎧ (1, 2, 3, n - 6) (1, 2, 5, n - 8) (1, 2, 6, n - 9) (2, 3, 5, n - 10)

\displaystyle \begin{cases} (1,2,3,n-6) \\ (1,2,5,n-8) \\ (1,2,6,n-9) \\ (2,3,5,n-10) \\ \end{cases}

Probar los casos tomará como máximo $4^{2} = 16$ 4^2=16 operaciones, lo cual es lo suficientemente rápido.

def solve():
    n=int(input())
    a=[1,2,3,n-6]
    b=[2,3,5,n-10]
    c=[1,2,5,n-8]
    d=[1,2,6,n-9]
    v=[a,b,c,d]
    for i in v:
        if(min(i)>0 and len(set(i))==4 and i[3]%4!=0):
            print(*i)
            return
    print(-1)

for _ in range(int(input())):
    solve()

Python

Complejidad $O (1)$ .