H - 変数の最大化
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
変数 a があり、初め a=X です。
i=1,2,\ldots,N の順に次の操作をします。
- 1 以上 m_i 以下の整数を選び、c とする。そして、a を以下の条件を満たす整数 a' の最小値に置き換える。
- a \lt a'
- a' の二進数表記にはちょうど c 個の
1
が含まれる
操作終了後の a の最大値を求めてください。
制約
- 1 \leq N \leq 50
- 0 \leq X \leq 1000
- 1 \leq m_i \leq 10
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X m_1 \ldots m_N
出力
答えを出力せよ。なお、本問の制約の下では答えが 10^{18} 以下になることが証明出来る。
入力例 1
1 11 2
出力例 1
16
c=1 として操作をすると a = 16 に、c=2 として操作をすると a=12 となります。
入力例 2
23 1000 2 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 2 2 8 7 7 9 8
出力例 2
4294967296
オーバーフローに注意してください。