# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Jeevan Jyot Singh

Tester: Jakub Safin, Satyam

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1162

# PREREQUISITES:

None

# PROBLEM:

Ved started playing a new mobile game called Fighting Clans. An army of N enemies is approaching his base. The i^{th} enemy has H_i health points. An enemy gets killed if his health points become 0.

Ved defends his base using a weapon named `Inferno`

. He can set the `Inferno`

to one of the following two modes:

- Single-Target Mode: In one second, the
`Inferno`

can target**exactly one**living enemy and cause damage of at most X health points. - Multi-Target Mode: In one second, the
`Inferno`

can target**all**living enemies and cause damage of 1 health point to each of them.

Find the **minimum** time required to kill all the enemies.

**Note:** Ved is **not allowed** to change the mode of the weapon once it is set initially.

# EXPLANATION:

Let us calculate answer for both modes:

- Single Target Mode: Here we would loop through each enemy and calculate the time required to kill him. Let us assume a function f(i) that tells the time taken to kill the i_{th} enemy then,

- Multi Target Mode: Here the answer would be the maximum H_i among all the enemies since each second it is reducing the health of all enemies by 1. Thus,

Once we calculate these two, our final answer would be:

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester1’s Solution

Tester2’s Solution