HackerRank : Week of Code 26 –Army Game

By | November 28, 2016
Army Game

Luke is daydreaming in Math class. He has a sheet of graph paper with n rows and m columns, and he imagines that there is an army base in each cell for a total of n.m bases. He wants to drop supplies at strategic points on the sheet, marking each drop point with a red dot. If a base contains at least one package inside or on top of its border fence, then it’s considered to be supplied. For example:

image

Given n and m, what’s the minimum number of packages that Luke must drop to supply all of his bases?

Input Format

Two space-separated integers describing the respective values of n and m.

Constraints

 0<n, m<=1000

Output Format

Print a single integer denoting the minimum number of supply packages Luke must drop.

Sample Input 0

2 2

Sample Output 0

1

Explanation 0

Luke has four bases in a 2 X 2   grid. If he drops a single package where the walls of all four bases intersect, then those four cells can access the package:

image

Because he managed to supply all four bases with a single supply drop, we print 1 as our answer.

Solution

Logic seems to be twisted but is actually easy.
I have broken problem into chunks to solve it. The first condition I have taken is 
when n and m are equal. 
Second condition I have taken, when one of n or m is equal to 1. And then I have 
handled other cases all at once. 

Hint: 
4X4 = 4 drops. 
3X3 = 4 drops. 

6X6 = 9 drops. 
5X5 = 9 drops. 

Approach: 

Take both dimension inputs from user. 
If x is equal to y, i.e if it is a square, then we have seen that the bomb count of 
each even number is equal to its square divided by 4. 
If the dimensions are odd, then just add 1 and do the same calculation. 

Hint: 
4X4 = 4 drops. 
3X3 = 4 drops.
 
6X6 = 9 drops. 
5X5 = 9 drops. 

Next condition to check is check if both of the dimensions are 1, then the bomb count 
is 1. Now, if any one of the dimension is 1 then, check the other, if other one is 
odd, then do its half and add 1. if other dimension is even then just do the half of 
it to get the bomb count. Now if none of the above condition is met, then we do not 
have a square, and neither we have any dimension as 1. Means both are different dimensions. 
So, just make both even, i.e., if x is odd, add 1 to it. If y is odd, then 
add 1 to y. And, multiply x and y and divide the result by 4 to get the final bomb count. 

Code: 

import java.util.Scanner;

public class ArmyGame {
	
	public static void main(String[] args) {
		
		Scanner scan= new Scanner(System.in);
		int x=scan.nextInt(), y=scan.nextInt();
		
		int drop=0;
		
		if(x==y)
		{
			int fin=0;
			if(x%2!=0)
				fin=x+1;
			else
				fin=x;
			
		drop=(fin*fin)/4;	
		}
		else if(x ==1 && y==1)
		{
			drop=1;
		}
		else if(x ==1 || y==1)
		{
			if(x==1)
			{
				if(y%2==0)
					drop=y/2;
				else
					drop=(y/2)+1;
			}
			else
			{
				if(x%2==0)
					drop=x/2;
				else
					drop=(x/2)+1;
			}
		}
		else
		{
			if(x%2!=0)
				x=x+1;
			if(y%2!=0)
				y=y+1;
			
			drop=(x*y)/4;	
			
		}
		
		System.out.println(drop);
		
		
	}

}