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)的可怕怪物。

经过两个小时的游戏,沃瓦已追踪到该怪物并分析了它的战斗策略。魔蟹拥有 h2h_2 点生命值,攻击力为 a2a_2。得知这些信息后,沃瓦决定大量购买强力治疗药水,为战斗做好准备。

沃瓦的角色拥有 h1h_1 点生命值,攻击力为 a1a_1。此外,他拥有大量治疗药水,每瓶药水可使他当前的生命值增加 c1c_1(当他饮用一瓶药水时)。所有药水完全相同。题目保证 c1>a2c_1 > a_2。

战斗由若干轮(phases)组成。在每轮开始时,沃瓦可选择以下两种行动之一:

  • 攻击怪物(使怪物生命值减少 a1a_1);
  • 饮用一瓶治疗药水(使自身生命值增加 c1c_1;沃瓦的生命值可超过初始上限 h1h_1)。

随后,若战斗尚未结束,则魔蟹会反击沃瓦,使其生命值减少 a2a_2。当沃瓦或魔蟹的生命值降至 00 或更低时,战斗立即结束。注意:战斗可能在某一轮中沃瓦完成攻击后、魔蟹尚未反击前就已结束。

显然,沃瓦希望赢得这场战斗。同时,他也希望以尽可能快的方式获胜,即在最少的轮数内取得胜利。

请帮助沃瓦制定最优策略!你可以假设沃瓦永远不会用完治疗药水,且他总能获胜。

输入格式

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.

第一行包含三个整数 h1h_1、a1a_1、c1c_1(1 ≤ h1, a1 ≤ 1001 \le h_1, a_1 \le 100,2 ≤ c1 ≤ 1002 \le c_1 \le 100)—— 分别表示沃瓦的生命值、攻击力以及药水的治疗量。

第二行包含两个整数 h2h_2、a2a_2(1 ≤ h2 ≤ 1001 \le h_2 \le 100,1 ≤ a2 < c11 \le a_2 < c_1)—— 分别表示魔蟹的生命值和攻击力。

输出格式

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.

第一行输出一个整数 nn,表示赢得战斗所需的最少阶段数。

随后输出 nn 行。第 ii 行必须为 HEAL(若 Vova 在第 ii 阶段饮用药水)或 STRIKE(若他攻击 Modcrab)。

该策略必须合法:Vova 的角色在击杀 Modcrab 之前不得被击败,且在 Vova 执行最后一次操作后,怪物的生命值必须为 00 或更低。

若存在多个最优解,输出任意一个即可。

输入输出样例

  • 输入#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测评打分。不知道怎么写?

首页