Problem of The Day 13 December 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 n.m 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 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:

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

Problem Link: Army Game

Solution will be posted tomorrow.

SOLUTION

The most optimal way is to put bombs in in corners(crossings) because in this case bomb covers 4 adjacent cells. If the bomb is not in a corner, but in the middle of some edge then we can move it to some corner and it still will cover this cell and maybe some new. So we make square of 2x2 put the bomb at the corner crossing.
Now if n and m both are even then solution will be (n1*m1)/4
if any of n or m is odd the solution will be (n1*m1)/4 + (n1 or m1)/2
or if both are odd then solution will be (n1*m1)/4 + n1/2 + m1/2 + 1

If we make a general case then solution will be (n+1)(m+1)/4

CODE

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int ans=0;
    int n1=n/2,m1=m/2;
    ans = n1*m1;
    int rem_n,rem_m;
    rem_n  = n-n1*2;
    rem_m = m-m1*2;
    //cout<<rem_n<<rem_m<<endl;
    if(rem_n==0 && rem_m==0) // if both are even
    {
        ans=ans;
    }
    else if(rem_n==1 && rem_m==0) // if n is odd and m is even
    {
        ans+= m/2;
    }
    else if(rem_n==0 && rem_m==1) // if m is odd and n is even
    {
        ans+= n/2;
    }
    else //if both are odd
    {
        ans+=n/2+m/2+1;
    }
    cout<<ans<<endl;
}