G.W. Coding Contest 3 P5: Dungeon Escape

Andor is on his way to become the best adventurer in the world. Unfortunately, his journey is cut short when he finds himself trapped in a dungeon! To escape, he must pass through N rooms numbered from 1 to N, where room 1 is connected to 2 and so on. Each of the rooms contains exactly one monster.

All of the monsters and Andor have a specific amount of health, damage, and resistance, represented by H, R, and D respectively. When Andor initiates combat with a monster, they both lose health equal to their opponent's TOTAL damage. The total damage dealt is equal to the attacker's damage subtracted by the opponent's resistance, and attacks will always deal a minimum of 1 damage despite any resistance. This process will repeat until either the monster's health reaches 0 or is negative, allowing Andor to progress, or Andor's health reaches 0 or is negative, meaning he will never escape from the dungeon. If Andor loses health in combat, it does not restore for the next fight.

Luckily, Andor has one last invisibility potion that allows him to move without being detected, allowing him to skip combat with monsters. Unfortunately, this potion only lasts for one room.

Can Andor escape?

The first line contains the integer \(N\), the number of rooms in the dungeon.

The second line contains integers \(H\), \(D\), and \(R\), representing Andor's health, damage, and resistance.

The following \(N\) lines contains the integers \(h\)_i, \(d\)_i, and \(r\)_i, representing the health, damage, and resistance of the monster in room \(i\).

\(\{\text{1 } \leq N \leq 10^6 \}\)

{1 \(\leq\) \(H\), \(D\), \(R\), \(h\)_i, \(d\)_i, \(r\)_i \(\leq\) \(2^{31}\)}

Output 'Escape' if Andor can escape, or 'Trapped' if he cannot.

Submit Solution