No.2071 Shift and OR
タグ : / 解いたユーザー数 129
作問者 :
taiga0629kyopro
/ テスター :
遭難者
問題文
長さ $N$ の整数列 $A$ が与えられます。また整数 $x$ に対して関数 $\mathrm{shift}(x)$ を次のように定めます。
$$\mathrm{shift}(x)=\left \lfloor \frac{x}{2} \right \rfloor+2^{15} × (x\ \mathrm{mod}\ 2)$$
あなたは次の操作を何度でも行うことができます。($1$ 回も行わなくても良い。)
- $1 \le i \le N$ を満たす整数 $i$ を1つ選び、$A_i$ を $\mathrm{shift}(A_i)$ に置き換える。
操作後の $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ としてあり得る値のうち最大値を求めてください。 ただし、$\mathrm{OR}$ はビットごとの論理和を表します。
▶︎$\left \lfloor \frac{x}{2} \right \rfloor$ とは(クリックで開く)
$\left \lfloor \frac{x}{2} \right \rfloor$ で $x$ を $2$ で割った時の商を表します。
▶︎$x\ \mathrm{mod}\ 2$ とは(クリックで開く)
$x\ \mathrm{mod}\ 2$ で $x$ を $2$ で割った余りを表します。
入力
$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
操作を行った後の $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ の最大値を出力してください。
サンプル
サンプル1
入力
2 1 2
出力
49152
次のように操作を行います。
- $i=1$ とする。$A=(32768,2)$ となる。
- $i=2$ とする。$A=(32768,1)$ となる。
- $i=2$ とする。$A=(32768,32768)$ となる。
- $i=2$ とする。$A=(32768,16384)$ となる。
$A_1 \ \mathrm{OR} \ A_2=49152$ となり、これが最大です。
サンプル2
入力
3 6 2 9
出力
63488
サンプル3
入力
5 3 1 4 1 5
出力
65024
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。