Quad#11854

Quad (Corrigé)

Auteur du problème :	Hasan Saleh (MathModel)
Préparé par :	Hasan Saleh (MathModel)
Édité par :	Hasan Saleh (MathModel)

Solution 1 (Analyse Amortie)

Considérons l'algorithme naïf pour le code, qui consiste à itérer tous les $4$ entiers $(a, b, c, d)$ (a,b,c,d) avec une borne supérieure $n$ telle 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, et qu'ils ne soient pas tous divisibles par $4$ et aient une somme de $n$ .

Bien sûr, en théorie, cela est $O (n^{4})$ \mathcal{O}(n^4). Pouvons-nous optimiser ? Oui, nous pouvons supprimer $d$ , car

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

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

Nous avons maintenant un code en $O (n^{3})$ \mathcal{O}(n^3), et maintenant ? Il suffit de le soumettre, oui, le code est suffisamment efficace et en fait c'est $O (1)$ .

Preuve :

Remarquez que $(n \leq 10)$ (n \le 10) n'a pas de quad valide, donc imprimez simplement $- 1$ .

Sinon, considérons la première itération de $(a, b, c) = (1, 2, 3)$ (a,b,c)=(1,2,3), nous ne ferons plus d'itérations tant que $(n - a - b - c) mod 4 \neq = 0$ (n-a-b-c) \bmod 4 \neq 0 car cela satisfait toutes les conditions, donc pour le cas de $(n - (a + b + c)) mod 4 \neq = 0$ (n-(a+b+c)) \bmod 4 \neq 0, cela fait en fait une seule itération, ce qui signifie que pour $n mod 4 \neq = 2$ n \bmod 4 \neq 2, nous ferons une seule itération.

Que se passe-t-il lorsque $(n - (a + b + c)) mod 4 = 0$ (n-(a+b+c)) \bmod 4 =0 ? Vous passerez à $a = 2, b = 3, c = 5$ a=2,b=3,c=5 et vous aurez $d = n - 10$ d=n-10, $d mod 4 = 2$ d \bmod 4=2 ce qui est valide, donc vous ne ferez que $3$ itérations (puisque nous avons sauté $c = 4$ c=4).

Complexité $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

Complexité $O (1)$

Solution 2 (Cas par Cas) Vous pouvez décider de simplement traiter le code par cas, bien sûr, nous avons $2$ cas :

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

Ce cas n'a pas de solutions, donc imprimez simplement $- 1$ .

Lisez la solution de l'analyse amortie pour comprendre le point de traitement par cas ici.

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

Il y a $4$ constructions dont au moins une doit être vraie, il y a

⎩ ⎨ ⎧ (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}

Essayer les cas prendra au maximum $4^{2} = 16$ 4^2=16 opérations, ce qui est suffisamment rapide.

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

Complexité $O (1)$ .