Kvadrat#11854

Kvadrat (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll 1 (Amortizasiya Analizi)

Gəlin kod üçün sadə alqoritmi nəzərdən keçirək, bu, $4$ tam ədədi $(a, b, c, d)$ (a,b,c,d) $n$ yuxarı sərhəd ilə iterasiya etməklədir, belə ki, $b \geq a + 1$ b \ge a+1, $c \geq b + 1$ c \ge b+1, $d \geq c + 1$ d \ge c+1 və onların hamısı $4$ -ə bölünmür və cəmi $n$ -dir.

Təbiidir ki, nəzəri cəhətdən bu $O (n^{4})$ \mathcal{O}(n^4)-dür. Bunu optimallaşdıra bilərikmi? Bəli, $d$ -ni çıxara bilərik, çünki

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

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

İndi bizdə $O (n^{3})$ \mathcal{O}(n^3) kod var, indi nə? Sadəcə təqdim edin, bəli, kod kifayət qədər səmərəlidir və əslində bu $O (1)$ -dir.

Sübut:

Qeyd edin ki, $(n \leq 10)$ (n \le 10) üçün etibarlı kvadrat yoxdur, ona görə də sadəcə $- 1$ çap edin.

Əks halda, $(a, b, c) = (1, 2, 3)$ (a,b,c)=(1,2,3) ilk iterasiyanı nəzərdən keçirin, $(n - a - b - c) mod 4 \neq = 0$ (n-a-b-c) \bmod 4 \neq 0 olduğu müddətcə daha çox iterasiya etməyəcəyik, çünki bu, bütün şərtləri ödəyir, belə ki, $(n - (a + b + c)) mod 4 \neq = 0$ (n-(a+b+c)) \bmod 4 \neq 0 üçün əslində tək iterasiya aparır, yəni $n mod 4 \neq = 2$ n \bmod 4 \neq 2 tək iterasiya edəcək.

$(n - (a + b + c)) mod 4 = 0$ (n-(a+b+c)) \bmod 4 =0 olduqda nə baş verir? $a = 2, b = 3, c = 5$ a=2,b=3,c=5-ə keçəcəksiniz və $d = n - 10$ d=n-10 olacaq, $d mod 4 = 2$ d \bmod 4=2 ki, bu da etibarlıdır, beləliklə, yalnız $3$ iterasiya edəcəksiniz (çünki $c = 4$ c=4-ü keçmişik).

Komplekslik $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

Komplekslik $O (1)$

Həll 2 (Hal İşləri) Kodun hal işlərini aparmağı qərara ala bilərsiniz, əlbəttə, $2$ halımız var:

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

Bu halın həlli yoxdur, ona görə də sadəcə $- 1$ çap edin.

Mod üzrə hal işlərinin məntiqini başa düşmək üçün Amortizasiya Analizinə baxın.

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

Onlardan ən azı birinin mütləq olmalı olduğu $4$ quruluş var, bunlar:

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

Halları sınamaq ən çox $4^{2} = 16$ 4^2=16 əməliyyat alacaq ki, bu da kifayət qədər sürətlidir.

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

Komplekslik $O (1)$ .