Проблема "AND"#12233

Проблема "AND" (Розбір)

listings

Автор задачі:	Imran AKKI
Підготовлено:	Imran AKKI
Редакція:	Hasan Saleh (MathModel)

Розв'язок Ми знаємо факт, що для будь-яких $x, y \geq 0$ x,y \ge 0 виконується $x & y \leq min (x, y)$ x \& y \le \min(x,y), бо в кращому випадку вони ділять усі біти.

Ми хочемо показати, що послідовне виконання операції є оптимальним, бо щоразу відповідь або залишатиметься тією ж, або зменшуватиметься через визначення AND, тобто відповідь:

x = a_{1} & a_{2} & a_{3} &...& a_{n}

x=a_1 \& a_2 \& a_3 \& ... \& a_n

Симулюємо процес для $n = 3$ n=3

[a_{1}, a_{2}, .., a_{n}] \to [a_{1} & a_{2}, a_{1} & a_{2}, a_{3}] \to [a_{1} & a_{2} & a_{3}, a_{1} & a_{2}, a_{1} & a_{2} & a_{3}] \to [x, x, x]

[a_1,a_2,..,a_n] \rightarrow [a_1\&a_2,a_1\&a_2,a_3] \rightarrow [a_1\&a_2\&a_3,a_1\&a_2,a_1\&a_2\&a_3] \rightarrow [x,x,x]

Очевидно, що ми не можемо виконати більше операцій над масивом $a$ , і це мінімально можливе значення, тому оптимальна відповідь: $[n разів x, x, ..., x]$ [\underbrace{x,x,...,x}_{n\text{ разів}}], що еквівалентно нескінченному виконанню операції.

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    A=a[0]
    for i in a:
        A&=i
    print(A)

Python

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