Dexter's Payback

3.6

7 votes
Problem

Frustrated from Mandark's challenges, Dexter plans an invasion in Mandark's lab. He knows that the underground entrance is the best way to get inside. But still, he needs to defuse the bombs hidden under the tiles of the floor. Dexter knows that the entrance has rectangular floor, divided in 1x1 tiles, so he numbered the rows of tiles from 0 to Height-1 and columns from 0 to Width-1.

Each tile can contain at most one bomb, and the Euclidean distance between each pair of bombs must not equal 2. The Euclidean distance between tile in row x1, column y1 and tile in row x2, column y2 is defined as the square root from (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2).

INPUT

First line gives T, the number of test cases. Each test case gives Width and Height of the floor.

OUTPUT

For each test case, print the maximal number of stones Mandark can plant in the floor. CONSTRAINTS

  • 1 <= T<= 50
  • 1 <= Height, Width <= 1000
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For first case, Mandark can place four stones on the board. Here is one possible arrangement: - * * * * -

For second case, a possible arrangement can be: * - - * - - *

Editor Image

?