Le Problème du "And"#12233

Le Problème du "And" (Corrigé)

listings

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

Solution On sait que pour tous $x, y \geq 0$ x,y \ge 0, il est vrai que $x & y \leq min (x, y)$ x \& y \le \min(x,y) car au meilleur des cas ils partagent tous les bits.

On veut montrer que réaliser l'opération séquentiellement est optimal, car chaque fois la réponse restera soit la même, soit diminuera à cause de la définition de l'opérateur AND, c'est-à-dire que la réponse est

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

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

Simulons le processus pour $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]

Il est évident que nous ne pouvons plus effectuer d'opérations sur le tableau $a$ et que c'est la valeur minimale possible, donc la réponse optimale est $[n fois x, x, ..., x]$ [\underbrace{x,x,...,x}_{n\text{ fois}}], ce qui équivaut à effectuer l'opération un nombre infini de fois.

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

Complexité $O (n)$ .