Round 1

Questions:

Problem Statement:

There is an ongoing battle between heroes and villains. You have M heroes, each with the same initial health H. There are N villains, where the health of the i-th villain is given by V[i]. When a hero with health H fights a villain with health V[i], one of the following scenarios occurs:

If H > V[i] → The villain is defeated, and the hero’s health decreases by V[i]. If H < V[i] → The hero loses the fight and can no longer continue. The villain remains unaffected. If H = V[i] → Both the hero and the villain are defeated and cannot continue. Heroes fight villains in the given order (from the first villain to the last). If at any point all heroes are defeated before eliminating all villains, the villains win. To ensure victory for the heroes, you can remove some villains from the front of the list before the battle starts.

Your task is to determine the minimum number of villains to remove from the front to guarantee victory for the heroes.

Input Format:

• The first line contains an integer N (1 ≤ N ≤ 2 × 10^5), the number of villains.
• The second line contains an integer M (1 ≤ M ≤ 2 × 10^5), the number of heroes.
• The third line contains an integer H (1 ≤ H ≤ 10^9), the health of each hero.
• The next line contains N space-separated integers V[i] (1 ≤ V[i] ≤ 10^9), representing the health of each villain.

Output Format: Print a single integer: the minimum number of villains that must be removed from the front to ensure that all remaining villains can be defeated by the heroes.

Example 1: Input:

4
4
3
3 1 3 3

Output:

0

Explanation: Hero 1 fights Villain 1 → Both are defeated. Hero 2 fights Villain 2 → Wins, remaining health = 2. Hero 2 fights Villain 3 → Loses, villain remains with 3 HP. Hero 3 fights Villain 3 → Both are defeated. Hero 4 fights Villain 4 → Both are defeated. All villains are defeated, so no removals are needed.

Example 2: Input:

5
3
4
5 2 3 1 4

Output:

1

Explanation: If no villains are removed: Hero 1 fights Villain 1 → Loses (villain still has 5 HP). Remaining heroes cannot defeat all villains. Removing Villain 1 (health 5):

Hero 1 fights Villain 2 → Wins, remaining health = 2. Hero 1 fights Villain 3 → Loses, villain remains with 3 HP. Hero 2 fights Villain 3 → Both are defeated. Hero 3 fights Villain 4 → Wins, remaining health = 3. Hero 3 fights Villain 5 → Both are defeated. Now all villains are defeated, so the minimum removal needed is 1.

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---