#P6462. Hero Last-Hit Strategy
Hero Last-Hit Strategy
Hero Last-Hit Strategy
In this problem, you are given a scenario inspired by a MOBA game. When an enemy creep enters the range of your defensive tower, it will be continuously hit by the tower dealing $x$ damage per attack. Your hero can also attack the creep, dealing $y$ damage per attack. Both the tower and your hero have the same attack speed. This means that you have the option to attack before the tower’s first attack or immediately after every tower attack. Of course, you may also choose not to attack at any opportunity.
The creep initially has $h$ hit points. Once its health drops to \(\le 0\), it dies. In order to get the experience for the kill, you want to make sure that you deliver the killing blow. In other words, you want to be the one whose attack causes the creep's health to drop to \(\le 0\) before the tower can kill it.
For simplicity, we assume the following order of events:
- At the very beginning (round 0 pre-phase), you have the opportunity to attack once.
- If the creep is still alive, the tower attacks and subtracts \(x\) from its health.
- Then, still in round 0, you have the opportunity to attack once (post-phase).
- For every subsequent round, the tower attacks first (reducing the creep's health by \(x\)), after which you have one chance to attack.
Your task is to decide whether there is a strategy (i.e. a choice of which attack opportunities to use) such that you can deal the finishing blow. Formally, you are given three positive integers \(h\), \(x\), and \(y\). If you can plan your attacks so that at some moment immediately before your attack the creep's remaining health is a positive number \(\ell\) with \(\ell \le y\) (and the creep is still alive since the tower did not kill it prior to that moment), then you can kill the creep. Otherwise, you cannot.
Hint: One useful strategy is to avoid attacking until after the tower has attacked a few times, then use your attack opportunities in every round to reduce the creep’s health further so that eventually, after a tower attack, the creep’s health becomes \(\le y\) (but still positive) and you can deliver the final blow.
Mathematical formulation:
If you never attack before the finishing round, the creep’s health after \(n\) tower attacks is \(h - n \cdot x\). However, by using your attack opportunities in some rounds before the final blow, you effectively reduce the creep’s health further. Suppose you use your attack in \(k\) rounds in addition to the final killing blow. Then, just before the final attack, the creep’s health is
[ f(n, k) = h - n \cdot x - k \cdot y. ]
You want to find nonnegative integers \(n \ge 1\) and \(k\) (with at most one attack per round available) such that
[ 0 < h - n \cdot x - k \cdot y \le y. ]
Also note that if \(h \le y\), you can kill the creep immediately in the initial phase (round 0 pre-phase).
Determine if it is possible to schedule your attacks accordingly so that you secure the last hit.
inputFormat
The input consists of a single line containing three positive integers h, x, and y.
\(h\) represents the creep’s initial health, \(x\) is the damage dealt by the tower per attack, and \(y\) is the damage dealt by your hero per attack.
outputFormat
Output a single line with either YES
if the hero can secure the killing blow or NO
otherwise.
sample
20 6 5
YES