No.2071 Shift and OR
タグ : / 解いたユーザー数 131
作問者 :
taiga0629kyopro
/ テスター :
👑 Problem Statement
You are given an integer sequence $A$ of length $N$. For an integer $x$, define the function $\mathrm{shift}(x)$ as follows.
$$\mathrm{shift}(x)=\left \lfloor \frac{x}{2} \right \rfloor+2^{15} × (x\ \mathrm{mod}\ 2)$$
You may perform the following operation any number of times. (You do not have to perform it even $1$ time.)
- Choose 1 integer $i$ satisfying $1 \le i \le N$, and replace $A_i$ with $\mathrm{shift}(A_i)$.
Find the maximum possible value of $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ after the operations. Here, $\mathrm{OR}$ denotes bitwise OR.
▶︎What is $\left \lfloor \frac{x}{2} \right \rfloor$? (click to open)
$\left \lfloor \frac{x}{2} \right \rfloor$ denotes the quotient when $x$ is divided by $2$.
▶︎What is $x\ \mathrm{mod}\ 2$? (click to open)
$x\ \mathrm{mod}\ 2$ denotes the remainder when $x$ is divided by $2$.
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the maximum value of $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ after performing the operations.
Sample
Sample 1
Input
2 1 2
Output
49152
Perform the operations as follows.
- Let $i=1$. Then $A=(32768,2)$.
- Let $i=2$. Then $A=(32768,1)$.
- Let $i=2$. Then $A=(32768,32768)$.
- Let $i=2$. Then $A=(32768,16384)$.
Then $A_1 \ \mathrm{OR} \ A_2=49152$, and this is the maximum.
Sample 2
Input
3 6 2 9
Output
63488
Sample 3
Input
5 3 1 4 1 5
Output
65024
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。