codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

903B.md (2981B)


      1 Source: https://codeforces.com/problemset/problem/903/B
      2 
      3 B. The Modcrab
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 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.
     26 
     27 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.
     28 
     29 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.
     30 
     31 Help Vova to make up a strategy! You may assume that Vova never runs out of healing potions, and that he can always win.
     32 
     33 Input
     34 
     35 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.
     36 
     37 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.
     38 
     39 Output
     40 
     41 In the first line print one integer *n* denoting the minimum number of phases required to win the battle.
     42 
     43 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.
     44 
     45 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.
     46 
     47 If there are multiple optimal solutions, print any of them.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 10 6 100  
     55 17 5
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 4  
     62 STRIKE  
     63 HEAL  
     64 STRIKE  
     65 STRIKE
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 11 6 100  
     72 12 5
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 2  
     79 STRIKE  
     80 STRIKE
     81 ```
     82 
     83 Note
     84 
     85 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.
     86 
     87 In the second example no healing needed, two strikes are enough to get monster to zero health and win with 6 health left.