CF903B.The Modcrab
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Vova is again playing some computer game, now an RPG. In the game Vova's character received a quest: to slay the fearsome monster called Modcrab.
After two hours of playing the game Vova has tracked the monster and analyzed its tactics. The Modcrab has _h_2 health points and an attack power of _a_2. Knowing that, Vova has decided to buy a lot of strong healing potions and to prepare for battle.
Vova's character has _h_1 health points and an attack power of _a_1. Also he has a large supply of healing potions, each of which increases his current amount of health points by _c_1 when Vova drinks a potion. All potions are identical to each other. It is guaranteed that _c_1 > _a_2.
The battle consists of multiple phases. In the beginning of each phase, Vova can either attack the monster (thus reducing its health by _a_1) or drink a healing potion (it increases Vova's health by _c_1; Vova's health can exceed _h_1). Then, if the battle is not over yet, the Modcrab attacks Vova, reducing his health by _a_2. The battle ends when Vova's (or Modcrab's) health drops to 0 or lower. It is possible that the battle ends in a middle of a phase after Vova's attack.
Of course, Vova wants to win the fight. But also he wants to do it as fast as possible. So he wants to make up a strategy that will allow him to win the fight after the minimum possible number of phases.
Help Vova to make up a strategy! You may assume that Vova never runs out of healing potions, and that he can always win.
沃瓦再次玩起了某款电脑游戏,这次是一款角色扮演游戏(RPG)。在游戏中,沃瓦的角色接到一项任务:击败名为“魔蟹”(Modcrab)的可怕怪物。
经过两个小时的游戏,沃瓦已追踪到该怪物并分析了它的战斗策略。魔蟹拥有 h2 点生命值,攻击力为 a2。得知这些信息后,沃瓦决定大量购买强力治疗药水,为战斗做好准备。
沃瓦的角色拥有 h1 点生命值,攻击力为 a1。此外,他拥有大量治疗药水,每瓶药水可使他当前的生命值增加 c1(当他饮用一瓶药水时)。所有药水完全相同。题目保证 c1>a2。
战斗由若干轮(phases)组成。在每轮开始时,沃瓦可选择以下两种行动之一:
- 攻击怪物(使怪物生命值减少 a1);
- 饮用一瓶治疗药水(使自身生命值增加 c1;沃瓦的生命值可超过初始上限 h1)。
随后,若战斗尚未结束,则魔蟹会反击沃瓦,使其生命值减少 a2。当沃瓦或魔蟹的生命值降至 0 或更低时,战斗立即结束。注意:战斗可能在某一轮中沃瓦完成攻击后、魔蟹尚未反击前就已结束。
显然,沃瓦希望赢得这场战斗。同时,他也希望以尽可能快的方式获胜,即在最少的轮数内取得胜利。
请帮助沃瓦制定最优策略!你可以假设沃瓦永远不会用完治疗药水,且他总能获胜。
输入格式
The first line contains three integers _h_1, _a_1, _c_1 (1 ≤ _h_1, _a_1 ≤ 100, 2 ≤ _c_1 ≤ 100) — Vova's health, Vova's attack power and the healing power of a potion.
The second line contains two integers _h_2, _a_2 (1 ≤ _h_2 ≤ 100, 1 ≤ _a_2 < _c_1) — the Modcrab's health and his attack power.
第一行包含三个整数 h1、a1、c1(1 ≤ h1, a1 ≤ 100,2 ≤ c1 ≤ 100)—— 分别表示沃瓦的生命值、攻击力以及药水的治疗量。
第二行包含两个整数 h2、a2(1 ≤ h2 ≤ 100,1 ≤ a2 < c1)—— 分别表示魔蟹的生命值和攻击力。
输出格式
In the first line print one integer n denoting the minimum number of phases required to win the battle.
Then print n lines. i-th line must be equal to HEAL if Vova drinks a potion in i-th phase, or STRIKE if he attacks the Modcrab.
The strategy must be valid: Vova's character must not be defeated before slaying the Modcrab, and the monster's health must be 0 or lower after Vova's last action.
If there are multiple optimal solutions, print any of them.
第一行输出一个整数 n,表示赢得战斗所需的最少阶段数。
随后输出 n 行。第 i 行必须为 HEAL(若 Vova 在第 i 阶段饮用药水)或 STRIKE(若他攻击 Modcrab)。
该策略必须合法:Vova 的角色在击杀 Modcrab 之前不得被击败,且在 Vova 执行最后一次操作后,怪物的生命值必须为 0 或更低。
若存在多个最优解,输出任意一个即可。
输入输出样例
输入#1
10 6 100 17 5
输出#1
4 STRIKE HEAL STRIKE STRIKE
输入#2
11 6 100 12 5
输出#2
2 STRIKE STRIKE
说明/提示
In the first example Vova's character must heal before or after his first attack. Otherwise his health will drop to zero in 2 phases while he needs 3 strikes to win.
In the second example no healing needed, two strikes are enough to get monster to zero health and win with 6 health left.
在第一个例子中,沃瓦的角色必须在第一次攻击之前或之后进行治疗。否则,他的生命值将在两个阶段内降至零,而他需要三次攻击才能获胜。
在第二个例子中,无需治疗,两次攻击足以将怪物的生命值降至零,并以剩余 6 点生命值获胜。
输入解题思路,AI测评打分。不知道怎么写?