問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 22
作問者 : とりゐ / テスター : noya2 re_re0101 👑 qand
お気に入りにしたユーザー ProblemId : 6737 / 自分の提出
問題文最終更新日: 2021-07-30 03:24:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 307 (順位表) の他の問題:

Problem Statement

For a positive integer $n$, let $f(n)$ be the number of times $n$ can be divided by $2$. That is, $f(n)$ is defined as follows.

\[ f(n) = \begin{cases} f(n/2)+1 & (n \equiv 0 \pmod 2) \\ 0 & (n \equiv 1 \pmod 2) \end{cases} \] There are $N$ positive integers of $1$ digit. Among them, there are $c_i$ copies of $i$ $(1\leq i\leq9)$. Rearrange these $N$ integers and regard the result as an $N$-digit integer $M$ in base $10$. Find the maximum value of $f(M)$.

Input

$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$
  • All inputs are integers.

Output

Output the maximum value of $f(M)$.

Sample

Sample 1
Input
3
1 1 1 0 0 0 0 0 0
Output
3

There are $1,2,3$, with $1$ copy of each, and the possible values of $M$ are $123,132,213,231,312,321$.

  • $123=2^0\times123$, so $f(123)=0$
  • $132=2^2\times33$, so $f(132)=2$
  • $213=2^0\times213$, so $f(213)=0$
  • $231=2^0\times231$, so $f(231)=0$
  • $312=2^3\times39$, so $f(312)=3$
  • $321=2^0\times321$, so $f(321)=0$
Therefore, $f(M)$ takes its maximum value $3$ when $M=312$.

Sample 2
Input
5
0 0 1 0 2 2 0 0 0
Output
16

$f(M)$ takes its maximum value $16$ when $M=65536=2^{16}$.

Sample 3
Input
10
2 0 2 0 2 0 2 0 2
Output
0

All possible values of $M$ are odd.

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