← 返回题目列表

AtCoder · abc368_c

E. 三重攻击

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

分数: 300 点

问题陈述

您正在玩游戏。

有 N 敌人排成一排,然后 i前方第一个敌人的生命值为 H_i.

你将重复以下动作,直到所有敌人的生命值变为 0 或更少,使用变量 T 初始化为 0.

  • 增加 T by 1。然后,用生命值攻击最前面的敌人 1 或更多。如果 T 是的倍数 3,敌人的生命值减少 3;否则,它会减少 1.

查找值 T 当所有敌人的生命值变为 0 或更少。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq H_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
H_1 H_2 \ldots H_N

输出

打印答案。


示例输入 1

3
6 2 2

示例输出 1

8

执行的操作如下:

  • T 变为 1。攻击第一个敌人,其生命值变为 6-1=5.
  • T 变为 2。攻击第一个敌人,其生命值变为 5-1=4.
  • T 变为 3。攻击第一个敌人,其生命值变为 4-3=1.
  • T 变为 4。攻击第一个敌人,其生命值变为 1-1=0.
  • T 变为 5。攻击第二个敌人,其生命值变为 2-1=1.
  • T 变为 6。攻击第二个敌人,其生命值变为 1-3=-2.
  • T 变为 7。攻击第三个敌人,其生命值变为 2-1=1.
  • T 变为 8。攻击第三个敌人,其生命值变为 1-1=0.

示例输入 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

示例输出 2

82304529

示例输入 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 3

3000000000

注意整数溢出。