Квадрат#11854

Квадрат (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення 1 (Амортизований аналіз)

Розглянемо наївний алгоритм для коду, який полягає в ітерації всіх $4$ цілих чисел $(a, b, c, d)$ (a,b,c,d) з верхньою межею $n$ , таких що $b \geq a + 1$ b \ge a+1, $c \geq b + 1$ c \ge b+1, $d \geq c + 1$ d \ge c+1, і вони всі не діляться на $4$ та мають суму $n$ .

Звичайно, в теорії це $O (n^{4})$ \mathcal{O}(n^4). Чи можемо ми оптимізувати? Так, ми можемо прибрати $d$ , тому що

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

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

Тепер у нас є код $O (n^{3})$ \mathcal{O}(n^3), що далі? Просто надішліть його, так, код достатньо ефективний і насправді це $O (1)$ .

Доказ:

Зверніть увагу, що $(n \leq 10)$ (n \le 10) не має дійсного квадрата, тому просто виведіть $- 1$ .

В іншому випадку, розглянемо першу ітерацію $(a, b, c) = (1, 2, 3)$ (a,b,c)=(1,2,3), ми не будемо робити більше ітерацій, поки $(n - a - b - c) mod 4 \neq = 0$ (n-a-b-c) \bmod 4 \neq 0, оскільки це задовольняє всі умови, тому для випадку $(n - (a + b + c)) mod 4 \neq = 0$ (n-(a+b+c)) \bmod 4 \neq 0 насправді виконується одна ітерація, що означає, що для $n mod 4 \neq = 2$ n \bmod 4 \neq 2 буде виконано одну ітерацію.

Що коли $(n - (a + b + c)) mod 4 = 0$ (n-(a+b+c)) \bmod 4 =0? Ви перейдете до $a = 2, b = 3, c = 5$ a=2,b=3,c=5 і отримаєте $d = n - 10$ d=n-10, $d mod 4 = 2$ d \bmod 4=2, що є дійсним, отже, ви зробите лише $3$ ітерації (оскільки ми пропустили $c = 4$ c=4).

Складність $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

Складність $O (1)$

Рішення 2 (Розгляд випадків) Ви можете вирішити просто розглядом випадків, звичайно, у нас є $2$ випадки:

Випадок 1: $(1 \leq n \leq 10)$ (1 \le n \le 10):

Цей випадок не має рішень, тому просто виведіть $- 1$ .

Прочитайте Рішення до Амортизованого аналізу, щоб зрозуміти суть розгляду випадків за модулем тут]

Випадок 2: $n mod 4 \neq = 2$ n \bmod 4 \neq 2

Є $4$ конструкції, одна з яких принаймні повинна виконуватись, є

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

Спроба випадків займе не більше $4^{2} = 16$ 4^2=16 операцій, що є достатньо швидко.

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

Складність $O (1)$ .