103682: [Atcoder]ABC368 C - Triple Attack
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:5
Solved:0
Description
Score : $300$ points
Problem Statement
You are playing a game.
There are $N$ enemies lined up in a row, and the $i$-th enemy from the front has a health of $H_i$.
You will repeat the following action until the healths of all enemies become $0$ or less, using a variable $T$ initialized to $0$.
- Increase $T$ by $1$. Then, attack the frontmost enemy with health $1$ or more. If $T$ is a multiple of $3$, the enemy's health decreases by $3$; otherwise, it decreases by $1$.
Find the value of $T$ when the healths of all enemies become $0$ or less.
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1 \leq H_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $H_1$ $H_2$ $\ldots$ $H_N$
Output
Print the answer.
Sample Input 1
3 6 2 2
Sample Output 1
8
The actions are performed as follows:
- $T$ becomes $1$. Attack the 1st enemy, and its health becomes $6-1=5$.
- $T$ becomes $2$. Attack the 1st enemy, and its health becomes $5-1=4$.
- $T$ becomes $3$. Attack the 1st enemy, and its health becomes $4-3=1$.
- $T$ becomes $4$. Attack the 1st enemy, and its health becomes $1-1=0$.
- $T$ becomes $5$. Attack the 2nd enemy, and its health becomes $2-1=1$.
- $T$ becomes $6$. Attack the 2nd enemy, and its health becomes $1-3=-2$.
- $T$ becomes $7$. Attack the 3rd enemy, and its health becomes $2-1=1$.
- $T$ becomes $8$. Attack the 3rd enemy, and its health becomes $1-1=0$.
Sample Input 2
9 1 12 123 1234 12345 123456 1234567 12345678 123456789
Sample Output 2
82304529
Sample Input 3
5 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
3000000000
Beware of integer overflow.
Output
得分:300分
问题陈述
你在玩一个游戏。
有$N$个敌人排成一行,从前面数第$i$个敌人的血量为$H_i$。
你会重复以下操作,直到所有敌人的血量变为$0$或以下,使用一个初始化为$0$的变量$T$。
- 将$T$增加$1$。然后,攻击血量为$1$或以上的最前面的敌人。如果$T$是$3$的倍数,敌人的血量减少$3$;否则,减少$1$。
找出当所有敌人的血量变为$0$或以下时的$T$的值。
约束条件
- $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$。攻击第1个敌人,其血量变为$6-1=5$。
- $T$变为$2$。攻击第1个敌人,其血量变为$5-1=4$。
- $T$变为$3$。攻击第1个敌人,其血量变为$4-3=1$。
- $T$变为$4$。攻击第1个敌人,其血量变为$1-1=0$。
- $T$变为$5$。攻击第2个敌人,其血量变为$2-1=1$。
- $T$变为$6$。攻击第2个敌人,其血量变为$1-3=-2$。
- $T$变为$7$。攻击第3个敌人,其血量变为$2-1=1$。
- $T$变为$8$。攻击第3个敌人,其血量变为$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
注意整数溢出。