Defense

몬스터 한 마리를 잡기 위해 필요한 공격 횟수를

$$C=\left\lceil \frac{H}{K} \right\rceil$$

라고 하자.

어떤 몬스터도 소환된 순간부터 성에 도달하는 순간까지 최대 $N$번 공격받을 수 있다. 따라서 $C>N$이면 어떤 몬스터도 잡을 수 없으므로 답은 $0$이다.

이제 $C \le N$이라고 하자. 몬스터를 번갈아 공격하는 것보다, 잡을 수 있는 몬스터 하나를 정해 그 몬스터가 소멸할 때까지 공격하는 것이 손해가 아니다. 또한 잡을 수 있는 몬스터 중 성에 가장 가까운 몬스터를 먼저 잡는 것이 손해가 아니다.

전체적으로 공격할 수 있는 시간은 첫 몬스터가 소환되는 순간부터 마지막 몬스터가 성에 도달하는 순간까지이다. 이 시간은 총 $N+M-1$초이다. 한 몬스터를 잡는 데 $C$번의 공격이 필요하므로, 공격 횟수만 보면 최대

$$\left\lfloor \frac{N+M-1}{C} \right\rfloor$$

마리까지 잡을 수 있다. 당연히 전체 몬스터 수는 $M$마리이므로 답은

$$\min\left(M,\left\lfloor \frac{N+M-1}{C} \right\rfloor\right)$$

이다.

시간 복잡도는 테스트 케이스마다 $O(1)$이다.