問題一覧 > 通常問題

No.1633 Sorting Integers (Multiple of 2^K)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : とりゐとりゐ / テスター : noya2noya2 re_re0101re_re0101 遭難者遭難者
0 ProblemId : 6737 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-30 03:24:02

問題文

正の整数 $n$ に対して，$n$ を $2$ で割り切れる回数を $f(n)$ とします．すなわち，$f(n)$ を以下のように定義します．

\[ f(n) = \begin{cases} f(n/2)+1 & (n \equiv 0 \pmod 2) \\ 0 & (n \equiv 1 \pmod 2) \end{cases} \] $1$ 桁の正整数が $N$ 個あります．このうち $i$ は $c_i$ 個です $(1\leq i\leq9)$．これら $N$ 個の整数を並べ替え，それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき，$f(M)$ の最大値を求めてください．

入力

$N$
$c_1\ c_2\ c_3\ c_4\ c_5\ c_6\ c_7\ c_8\ c_9$

  • $1\leq N\leq 14$
  • $c_i\geq0$
  • $\displaystyle \sum_{i=1}^9 c_i=N$
  • 入力は全て整数である

出力

$f(M)$ の最大値を出力してください．

サンプル

サンプル1
入力
3
1 1 1 0 0 0 0 0 0
出力
3

$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．

  • $123=2^0\times123$ より $f(123)=0$
  • $132=2^2\times33$ より $f(132)=2$
  • $213=2^0\times213$ より $f(213)=0$
  • $231=2^0\times231$ より $f(231)=0$
  • $312=2^3\times39$ より $f(312)=3$
  • $321=2^0\times321$ より $f(321)=0$
したがって $M=312$ のとき $f(M)$ は最大値 $3$ をとります．

サンプル2
入力
5
0 0 1 0 2 2 0 0 0
出力
16

$M=65536=2^{16}$ のとき $f(M)$ は最大値 $16$ をとります．

サンプル3
入力
10
2 0 2 0 2 0 2 0 2
出力
0

$M$ として考えられるものは全て奇数です．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。