Posted onFeb 26 • Originally published atmmzeynalli.dev

Solving DSA Problems. CodeForces 1918-A: Brick Wall

Problem statement

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

A brick is a strip of size1 × k,placed horizontally or vertically, wherekcan be an arbitrary number that is at least2(k ≥ 2).

A brick wall of sizen × mis such a way to place several bricks inside a rectanglen × m,that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of then × mrectangle belongs to exactly one brick. Herenis the height of the rectanglen × mandmis the width.Notethat there can be bricks with different values of k in the same brick wall.

The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks.Notethat if you used0horizontal bricks and2vertical ones, then the stability will be−2, not 2.

What is the maximal possible stability of a wall of sizen × m?

It is guaranteed that under restrictions in the statement at least onen × mwall exists.

Input

The first line of the input contains one integert(1 ≤ t ≤ 10000), the number of test cases.

The only line of each test case contains two integersnandm(2 ≤ n,m ≤ 10^4).

Output

For each test case, print one integer, the maximum stability of a wall of sizen × m.

Example

input

5
2 2
7 8
16 9
3 5
10000 10000

output

2
28
64
6
50000000

Solution

Note: in notationa × b,ais height,bis width.

Even though it seems as a hard problem where you need to calculate different combination of brick lengths and their layout, it is quite easy problem. I chose this problem in order to demonstrate how some problems can be solved easily, without complicating things. When one does many hard problems, they are used to think complicated. So when an easy problem comes, they go into task with that complicated focused mindset and miss simple things (happened to me a lot in chess).

So, what we know:

We need to minimize vertical bricks and maximize the horizontal ones
Then, we need to use smallest bricks, to maximize the benefit: 2x1
We need to avoid using vertical bricks at all

So, if we use1 × 2bricks horizontally, we would havem / 2bricks in one layer, and that beingnlayers. Easy right? However, what ifmis odd? then we would have column left. We can fill it with vertical bricks, however, each vertical brick is decreases stability. So, how do we fill that gap? Easy, we just make the last brick of the row1 × 3instead of1 × 2.In a result, all bricks are placed horizontal, and their count beingfloor(m / 2) × n:

#include<stdio.h>

intmain()
{
intn,m,t;

scanf("%d",&t);

while(t--)
{
scanf("%d %d",&n,&m);
printf("%d\n",m/2*n);
}

return0;
}

NOTE:The statementm / 2should happen first, as we need floor down the division (we do it by using just integer division, no need for extra functions). Otherwise, you would get wrong result.