HackerRank : Week of Code 32 – Fight the Monsters

By | May 17, 2017
Fight the Monsters : Hackerrank

Fight the Monsters – Jason is trapped in a forest with hungry monsters and must use his trusty blaster to defend himself! Each monster has a health value, . Jason can discharge his blaster at a monster once per second and reduce its health points by units. Once a monster’s health points become , it dies.

Given the health values for each monster and an integer, , can you determine the maximum number of monsters he can kill in seconds? Assume Jason always hits his target!

Input Format

The first line consists of three space-separated integers describing the respective values of , , and .
The second line consists of space-separated integers describing the values of .

Constraints
Output Format
Print an integer denoting the maximum number of monsters Jason can kill in seconds.
Sample Input 0

7 8 6
16 19 7 11 23 8 16

Sample Output 0

4

Explanation 0

We want to find the maximum number of monsters we can kill in seconds using a blaster that does units of damage per second. The diagram below depicts the array of initial health values, :

image

The optimal approach is as follows:

  1. Shoot monster so , monster dies, and becomes :image
  2. Shoot monster so , monster dies, and becomes :image
  3. Shoot monster so and becomes :image
  4. Shoot monster again so , monster dies, and becomes :
    image
  5. Shoot monster so and becomes :
    image
  6. Shoot monster again so , monster dies, and becomes :image

Thus, we print as the maximum number of monsters we can kill in the given time period.

Solution

Straight forward problem.
Hint: No need to divide each time. You can store some values directly in array in such
a way that you can know how much units it will take to kill each monster.

Code:

package weekOfCode32;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class FightTheMonsters {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		double h = scan.nextInt();
		int t = scan.nextInt();
		ArrayList health = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			int item = scan.nextInt();
			health.add((int) Math.ceil(item / h));
		}

		Collections.sort(health);

		for (int j = 0; j < health.size(); j++) {
			int val = health.get(j);
			if (val <= t) {
				t = t - val;
				health.remove(j);
				health.add(j, 0);
			}
		}

		int count = 0;
		for (Integer integer : health) {
			if (integer == 0)
				count++;
			else
				break;
		}
		System.out.println(count);
	}

}