[ARC146B] Plus and AND
配点 : 点
問題文
長さ の非負整数列 が与えられます。あなたは以下の操作を 回以下行うことができます。( 回も行わなくてもよいです。)
- を満たす整数 を選び、 を 増やす。
その後、 の中から 要素を選びます。
選んだ 要素のビット単位 の最大値を求めてください。
ビット単位 $\mathrm{AND}$ 演算とは
整数 $A, B$ のビット単位 $\mathrm{AND}$、$A\ \mathrm{AND}\ B$ は以下のように定義されます。
- $A\ \mathrm{AND}\ B$ を二進表記した際の $2^k$ ($k \geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち両方が $1$ であれば $1$、そうでなければ $0$ である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{AND} は (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
4 8 2
1 2 4 8
10
以下のような手順を踏むことで 選んだ 要素の として を達成できます。
- を選ぶ操作を 回行う。 となる。
- を選ぶ操作を 回行う。 となる。
- を選ぶ。 要素の は である。
選んだ 要素の を 以上にすることはできないので、解は です。
5 345 3
111 192 421 390 229
461