← 返回题目列表

AtCoder · awc0059_a

A. 卡牌对战

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥正在玩纸牌游戏。

N 卡片在桌子上排成一排。的 i从左边算起第一张牌称为“牌” i”,和卡 i 的攻击力为 A_i 。

Takahashi 对每个操作执行一次以下操作 i,按顺序 i = 1, 2, \ldots, N-1。请注意,该操作针对的是带有 号码 i 和 i+1,不是桌子上物理相邻的牌。即使将卡从牌桌上移除,其号码也不会改变。

  • 如果至少一张卡 i 和卡 i+1 已从表中删除,无需执行任何操作。
  • 如果两张卡 i 和卡 i+1 留在桌子上,比较他们当前的攻击力。
  • 如果他们的攻击力相等,则不执行任何操作。
  • 如果攻击力不同,则攻击力较高的卡 吸收 其他。具体来说,当一张卡具有攻击力时 X 吸收一张具有攻击力的卡牌 Y (X > Y),会发生以下情况:
  • 被吸收的卡牌(具有攻击力 Y) 将从表中删除,并在后续操作中被视为不再位于表中。
  • 吸收卡保留在桌面上,且编号相同,其攻击力更新为 X + \lfloor Y / 2 \rfloor,其中 \lfloor \cdot \rfloor 表示下取整函数(向下舍入到最接近的整数)。更新后的攻击力将在后续行动中使用。

请注意,由于卡牌的攻击力可以通过吸收而改变,因此使用每次操作时的最新攻击力进行比较。

完成所有操作后 i = N-1 已完成,求桌子上剩余的牌数。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 代表卡片数量。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每张卡牌的攻击力。

输出

在一行中打印所有操作完成后桌子上剩余的卡片数量。


示例输入 1

5
3 1 4 1 5

示例输出 1

3

示例输入 2

4
2 2 2 2

示例输出 2

4

示例输入 3

10
5 3 8 6 2 7 1 9 4 10

示例输出 3

5

示例输入 4

20
100 37 85 12 99 44 67 23 78 56 91 33 72 15 88 41 63 29 50 1000000000

示例输出 4

10

示例输入 5

1
1

示例输出 5

1