El Problema del AND#12233

El Problema del AND (Editorial)

listings

Autor del Problema:	Imran AKKI
Preparado por:	Imran AKKI
Editado por:	Hasan Saleh (MathModel)

Solución Sabemos que para cualquier $x, y \geq 0$ x,y \ge 0 se cumple que $x & y \leq min (x, y)$ x \& y \le \min(x,y) porque en el mejor de los casos comparten todos los bits.

Queremos mostrar que realizar la operación secuencialmente es óptimo, porque cada vez la respuesta permanecerá igual o disminuirá debido a la definición de AND, es decir, la respuesta es

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

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

Simulemos el proceso para $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]

Es obvio que no podemos hacer más operaciones sobre el arreglo $a$ y ese es el valor mínimo posible, así que la respuesta óptima es $[n veces x, x, ..., x]$ [\underbrace{x,x,...,x}_{n\text{ veces}}], lo cual es equivalente a realizar la operación un número infinito de veces.

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

Complejidad $O (n)$ .