103512: [Atcoder]ABC351 C - Merge the balls
Description
Score: $250$ points
Problem Statement
You have an empty sequence and $N$ balls. The size of the $i$-th ball $(1 \leq i \leq N)$ is $2^{A_i}$.
You will perform $N$ operations.
In the $i$-th operation, you add the $i$-th ball to the right end of the sequence, and repeat the following steps:
- If the sequence has one or fewer balls, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.
Determine the number of balls remaining in the sequence after the $N$ operations.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the number of balls in the sequence after the $N$ operations.
Sample Input 1
7 2 1 1 3 5 3 3
Sample Output 1
3
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size $2^2$.
- After the second operation, the sequence has two balls, of sizes $2^2$ and $2^1$ in order.
- After the third operation, the sequence has one ball, of size $2^3$. This is obtained as follows:
- When the third ball is added during the third operation, the sequence has balls of sizes $2^2, 2^1, 2^1$ in order.
- The first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^1 + 2^1 = 2^2$ is added. Now, the sequence has balls of sizes $2^2, 2^2$.
- Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^2 + 2^2 = 2^3$ is added, leaving the sequence with a ball of size $2^3$.
- After the fourth operation, the sequence has one ball, of size $2^4$.
- After the fifth operation, the sequence has two balls, of sizes $2^4$ and $2^5$ in order.
- After the sixth operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^3$ in order.
- After the seventh operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^4$ in order.
Therefore, you should print $3$, the final number of balls in the sequence.
Sample Input 2
5 0 0 0 1 2
Sample Output 2
4
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size $2^0$.
- After the second operation, the sequence has one ball, of size $2^1$.
- After the third operation, the sequence has two balls, of sizes $2^1$ and $2^0$ in order.
- After the fourth operation, the sequence has three balls, of sizes $2^1$, $2^0$, $2^1$ in order.
- After the fifth operation, the sequence has four balls, of sizes $2^1$, $2^0$, $2^1$, $2^2$ in order.
Therefore, you should print $4$, the final number of balls in the sequence.
Output
问题描述
你有一个空序列和 $N$ 个球。第 $i$ 个球（$1 \leq i \leq N$）的大小为 $2^{A_i}$。
你将进行 $N$ 个操作。 在第 $i$ 次操作中，你将第 $i$ 个球添加到序列的右端，并重复执行以下步骤：
- 如果序列中有一个或更少的球，结束该操作。
- 如果序列中最右侧的球和次右侧的球的大小 不同，结束该操作。
- 如果序列中最右侧的球和次右侧的球的大小 相同，则移除这两个球，并在序列的右端添加一个新的球，其大小等于被移除的两个球的大小之和。然后，回到步骤1并重复该过程。
确定在 $N$ 次操作后序列中剩余的球的数量。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$
- 所有输入值均为整数。
输入
输入从标准输入按以下格式给出：
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印出 $N$ 次操作后序列中的球数量。
样例输入 1
7 2 1 1 3 5 3 3
样例输出 1
3
操作过程如下：
- 第一次操作后，序列中有1个球，大小为 $2^2$。
- 第二次操作后，序列中有2个球，按顺序大小分别为 $2^2$ 和 $2^1$。
- 第三次操作后，序列中有1个球，大小为 $2^3$。具体过程如下：
- 在第三次操作中，当添加第三个球时，序列中有大小分别为 $2^2$、$2^1$、$2^1$ 的球。
- 从右往左数第一个和第二个球大小相同，所以移除这两个球，并添加一个大小为 $2^1 + 2^1 = 2^2$ 的球。现在，序列中有大小分别为 $2^2$、$2^2$ 的球。
- 再次从右往左数第一个和第二个球大小相同，所以移除这两个球，并添加一个大小为 $2^2 + 2^2 = 2^3$ 的球，最后序列中只剩下一个大小为 $2^3$ 的球。
- 第四次操作后，序列中有1个球，大小为 $2^4$。
- 第五次操作后，序列中有2个球，按顺序大小分别为 $2^4$ 和 $2^5$。
- 第六次操作后，序列中有三个球，按顺序大小分别为 $2^4$、$2^5$、$2^3$。
- 第七次操作后，序列中有三个球，按顺序大小分别为 $2^4$、$2^5$、$2^4$。
因此，你应该打印出 $3$，即序列中最终剩余的球的数量。
样例输入 2
5 0 0 0 1 2
样例输出 2
4
操作过程如下：
- 第一次操作后，序列中有1个球，大小为 $2^0$。
- 第二次操作后，序列中有1个球，大小为 $2^1$。
- 第三次操作后，序列中有两个球，按顺序大小分别为 $2^1$ 和 $2^0$。
- 第四次操作后，序列中有三个球，按顺序大小分别为 $2^1$、$2^0$、$2^1$。
- 第五次操作后，序列中有四个球，按顺序大小分别为 $2^1$、$2^0$、$2^1$、$2^2$。
因此，你应该打印出 $4$，即序列中最终剩余的球的数量。