This post is dedicated to Hackerrank 'Army game problem'.
Here is the question:
Luke is daydreaming in Math class. He has a sheet of graph paper with rows and columns, and he imagines that there is an army base in each cell for a total of 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:
Given and , 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 and .
Constraints
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 grid. If he drops a single package where the walls of all four bases intersect, then those four cells can access the package:
Because he managed to supply all four bases with a single supply drop, we print as our answer.
Answer:
There are multiple approaches to solve this but I would like you guys to try it for some time then look below.
I know you guys did not try , just googled it :D.
You can consider this as denomination problem where you need to split the matrix in amounts of 2X2 , 1X2 and 1X1. This is a broad solution and a bit tricky as well ,since you need to keep a count each and every row.
For the next bit think a bit out of the box. I mean literally out of the box .
Now try and cover this whole by just 2X2 even if you go out of the box.
Give it some time use a paper and pen you will find the pattern hidden there only.
Let me break it down for you.
Consider a 10X6 matrix
Now for a 10X5 matrix :
Total Number of supply drops are same in both cases.
Since 10X5 and 10X6 could be fit in 10X6 matrix.
Now test for odd row and column. It has a bit of tweak in it.
I have pasted the code in C++ for your reference. I know you will copy it . So go ahead.
I am not saying it is most optimized code since there is always a room for optimization. Wrote it as I thought about it. Hope you find it useful.
CODE:
int main(){
int n;
int m;
cin >> n >> m;
int twobytwo = (m / 2) * (n / 2);
int factor =0;
if( (m%2 ==1) && (n%2 ==1) ){
factor = ( (m/2 +1) + ((n-1) /2) );
}else if(m%2 == 1){
factor = n/2;
}else if(n%2 == 1){
factor = m/2;
}
cout <<(twobytwo+factor);
return 0;
}
int n;
int m;
cin >> n >> m;
int twobytwo = (m / 2) * (n / 2);
int factor =0;
if( (m%2 ==1) && (n%2 ==1) ){
factor = ( (m/2 +1) + ((n-1) /2) );
}else if(m%2 == 1){
factor = n/2;
}else if(n%2 == 1){
factor = m/2;
}
cout <<(twobytwo+factor);
return 0;
}