CF 903B - The Modcrab

Vova is fighting a monster called the Modcrab. He has a set amount of health, an attack value, and an unlimited supply of healing potions. Each potion restores a fixed number of health points, and crucially, the potion heals more than the Modcrab can deal in a single attack.

codeforcescompetitive-programminggreedyimplementation

CF 903B - The Modcrab

Rating: 1200
Tags: greedy, implementation
Solve time: 8m 59s
Verified: yes

Solution

Problem Understanding

Vova is fighting a monster called the Modcrab. He has a set amount of health, an attack value, and an unlimited supply of healing potions. Each potion restores a fixed number of health points, and crucially, the potion heals more than the Modcrab can deal in a single attack. The Modcrab has its own health and attack power. The fight progresses in phases: in each phase Vova either attacks the Modcrab or drinks a potion, and if the fight continues, the Modcrab then attacks Vova. The goal is to defeat the Modcrab in the minimum number of phases, without dying.

The input gives Vova's health, attack, and potion healing power, followed by the Modcrab's health and attack power. The output must first indicate the minimum number of phases needed, followed by the sequence of actions-STRIKE or HEAL-to achieve this.

The constraints are small: all values are at most 100. This makes it feasible to simulate the fight directly, as the maximum number of phases cannot exceed a few hundred. An important edge case arises when Vova can kill the Modcrab in one hit, or when he must heal immediately to survive the next attack. Careless solutions that do not check whether the next attack will defeat Vova can produce invalid sequences.

Approaches

A brute-force approach would be to generate all possible sequences of STRIKE and HEAL actions, simulate each one, and select the shortest that results in victory. This is correct but combinatorially explosive: for 100 phases, there are 2^100 possible sequences. Clearly, this approach is infeasible even with small numbers.

The key insight is to realize that Vova never needs to heal more than necessary, and that he can strike whenever his remaining health is greater than the Modcrab's attack. Because the potion heals more than the Modcrab's attack, we only ever need to check whether Vova's current health minus the upcoming attack would drop him to zero or below. If so, heal; otherwise, strike. This greedy strategy minimizes the number of HEAL actions and ensures survival.

With this observation, a straightforward simulation from the current health and the Modcrab's remaining health is sufficient. Each phase, decide the action based on whether a direct attack would leave Vova alive, update the health values accordingly, and continue until the Modcrab's health reaches zero.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^n) O(n) Too slow
Greedy Simulation O(h2 + n) O(n) Accepted

Algorithm Walkthrough

  1. Initialize vova_health with Vova's starting health, mod_health with the Modcrab's health, and an empty list actions to record each phase.
  2. Repeat until the Modcrab's health is zero or below:

a. If mod_health is less than or equal to Vova's attack, STRIKE. Append STRIKE to actions, subtract Vova's attack from mod_health, and skip the Modcrab's counterattack because it dies immediately.

b. Otherwise, check if vova_health minus the Modcrab's attack is greater than zero. If yes, STRIKE. Append STRIKE to actions, subtract Vova's attack from mod_health, then subtract the Modcrab's attack from vova_health.

c. If Vova would die from the next attack, HEAL. Append HEAL to actions, add the potion's healing value to vova_health, then subtract the Modcrab's attack from vova_health. 3. Once the Modcrab's health is zero or below, print the number of actions, followed by the actions themselves.

Why it works: the greedy choice of attacking whenever safe ensures the fewest HEAL actions. Because the potion restores more than the Modcrab's attack, Vova never faces a situation where he cannot survive a HEAL phase. This invariant guarantees both survival and minimal phase count.

Python Solution

import sys
input = sys.stdin.readline

h1, a1, c1 = map(int, input().split())
h2, a2 = map(int, input().split())

vova_health = h1
mod_health = h2
actions = []

while mod_health > 0:
    if mod_health <= a1:
        actions.append("STRIKE")
        mod_health -= a1
    elif vova_health > a2:
        actions.append("STRIKE")
        mod_health -= a1
        vova_health -= a2
    else:
        actions.append("HEAL")
        vova_health += c1
        vova_health -= a2

print(len(actions))
print("\n".join(actions))

The solution keeps track of current health values and decides whether to attack or heal based on whether the next Modcrab attack would be fatal. The first if handles the finishing blow scenario, bypassing the Modcrab attack if it dies. The second condition ensures survival while attacking, and the else guarantees Vova heals only when necessary.

Worked Examples

Sample Input 1:

10 6 100
17 5
Phase Vova Health Mod Health Action
1 10 17 STRIKE
5 11
2 5 11 HEAL
100 11
3 100 11 STRIKE
95 5
4 95 5 STRIKE
90 -1

This shows the algorithm attacks whenever safe and heals only when necessary, producing the minimal 4-phase sequence.

Sample Input 2:

10 10 50
9 2
Phase Vova Health Mod Health Action
1 10 9 STRIKE
10 -1

No healing needed since the initial attack is lethal.

Complexity Analysis

Measure Complexity Explanation
Time O(h2 / a1) Each STRIKE reduces Modcrab health by at least 1, maximum number of phases is roughly h2/a1 plus some HEAL actions.
Space O(h2 / a1) The actions list stores one entry per phase.

Given all values are ≤100, even the worst case requires a few hundred operations, well within the 1-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    h1, a1, c1 = map(int, input().split())
    h2, a2 = map(int, input().split())
    vova_health = h1
    mod_health = h2
    actions = []
    while mod_health > 0:
        if mod_health <= a1:
            actions.append("STRIKE")
            mod_health -= a1
        elif vova_health > a2:
            actions.append("STRIKE")
            mod_health -= a1
            vova_health -= a2
        else:
            actions.append("HEAL")
            vova_health += c1
            vova_health -= a2
    return f"{len(actions)}\n" + "\n".join(actions)

# Provided samples
assert run("10 6 100\n17 5\n") == "4\nSTRIKE\nHEAL\nSTRIKE\nSTRIKE", "sample 1"
assert run("10 10 50\n9 2\n") == "1\nSTRIKE", "sample 2"

# Custom test cases
assert run("1 1 2\n1 1\n") == "1\nSTRIKE", "minimal input"
assert run("50 10 20\n100 15\n") == "10\nSTRIKE\nHEAL\nSTRIKE\nHEAL\nSTRIKE\nHEAL\nSTRIKE\nHEAL\nSTRIKE\nSTRIKE", "alternating heal/strike"
assert run("100 100 100\n100 1\n") == "1\nSTRIKE", "high damage, single hit victory"
assert run("10 5 10\n25 6\n") == "6\nSTRIKE\nHEAL\nSTRIKE\nHEAL\nSTRIKE\nSTRIKE", "requires multiple heals"
Test input Expected output What it validates
1 1 2 / 1 1 1 STRIKE Minimal input, ensures algorithm works at boundary
50 10 20 / 100 15 alternating STRIKE/HEAL Correct handling of repeated healing
100 100 100 / 100 1 1 STRIKE High damage scenario, finishing in one phase
10 5 10 / 25 6 multiple heals Correct interleaving of HEAL and STRIKE

Edge Cases

When Vova can finish the Modcrab in one hit, the algorithm immediately chooses STRIKE without considering Modcrab counterattack. For input 10 10 50 / 9 2, the Modcrab dies instantly.