No.3281 Pacific White-sided Dolphin vs Monster
タグ : / 解いたユーザー数 53
作問者 :
hirayuu_yc
/ テスター :
highlighter
Problem Statement
This time, Kamairuka (Pacific White-sided Dolphin) is going to fight Cerulean monsters.
Put simply, Kamairuka's special skill increases the damage she deals once it is activated.
Let us simplify this and assume that "the damage dealt becomes $2$ times as large with each passing turn". In reality, it is not quite that extremely strong, though.
There are $N$ Ceruleans. The Ceruleans are numbered $1,2,\dots,N$, and the HP of Cerulean $i$ is $H_i$.
Let $p$ be Kamairuka's attack power. Initially, $p=1$. Kamairuka can attack the Ceruleans any number of times. An attack is as follows.
- Choose any Cerulean and decrease its HP by $p$. A Cerulean whose HP becomes $0$ or less disappears. Then, the value of $p$ becomes $2$ times as large.
Find the minimum number of attacks required to make all the Ceruleans disappear. Here, Kamairuka is sufficiently strong and will never be defeated.
Input
$N$ $H_1$ $H_2$ $\dots$ $H_N$
- $1\leq N\leq 10^5$
- $1\leq H_i\leq 10^{18}$
- All inputs are integers.
Output
Output the answer.
Sample
Sample 1
Input
3 9 2 4
Output
4
All the Ceruleans can be made to disappear with $4$ attacks as follows.
- Decrease the HP of Cerulean $1$ by $p$ $(=1)$, making it $8$. Now $p=2$.
- Decrease the HP of Cerulean $2$ by $p$ $(=2)$, making it $0$. Cerulean $2$ disappears. Now $p=4$.
- Decrease the HP of Cerulean $3$ by $p$ $(=4)$, making it $0$. Cerulean $3$ disappears. Now $p=8$.
- Decrease the HP of Cerulean $1$ by $p$ $(=8)$, making it $0$. Cerulean $1$ disappears. Now $p=16$.
It can be shown that it is impossible to make all the Ceruleans disappear with $3$ or fewer attacks, so the answer is $4$.
Sample 2
Input
1 924
Output
10
Overkill is not a problem.
Sample 3
Input
6 924 924924 924924924 924924924924 924924924924924 924924924924924924
Output
60
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。