# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Soumyadeep Pal

Tester: Takuki Kurokawa

Editorialist: Yash Kulkarni

# DIFFICULTY:

968

# PREREQUISITES:

# PROBLEM:

You have a grid with N rows and M columns. You have two types of dominos - one of dimensions 2 * 2 and the other of dimensions 1 * 1. You want to cover the grid using these two types of dominos in such a way that :

- Each cell of the grid is covered by exactly one domino.
- The number of 1 * 1 dominos used is minimized.

Find the **minimum** number of 1 * 1 dominos you have to use to fill the grid.

# EXPLANATION:

The minimum number 1 * 1 dominos can be found by finding the maximum number of 2 * 2 dominos that can be placed in the grid. This is because the total area to be covered is constant (N * M).

We know that in each row we can place at most \lfloor N/2 \rfloor number of 2 * 2 dominos and in each column we can place at most \lfloor M/2 \rfloor number of 2 * 2 dominos. It is clear that we can always fill a sub-grid of size (\lfloor N/2 \rfloor * 2) * (\lfloor M/2 \rfloor * 2) with 2 * 2 dominos and this means that the maximum number of 2 * 2 dominos is \lfloor N/2 \rfloor * \lfloor M/2 \rfloor.

Since the total area to be covered is N * M and the maximum area to be covered by 2 * 2 dominos is 4 * \lfloor N/2 \rfloor * \lfloor M/2 \rfloor. So the minimum number of 1 * 1 dominos (= area to be covered by 1 * 1 dominos) is N * M - 4 * \lfloor N/2 \rfloor * \lfloor M/2 \rfloor.

# TIME COMPLEXITY:

O(1) for each test case.

# SOLUTION:

## Setter's solution

```
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
cout << n * m - 4 * (n / 2) * (m / 2) << '\n';
}
}
```

## Editorialist's Solution

```
using namespace std;
int main() {
int T;
cin >> T;
while(T--){
int n,m;
cin >> n >> m;
cout << m*n-(n/2)*(m/2)*4 << endl;
}
return 0;
}
```