Anti Light’s Cell Guessing solution codeforces
You are playing a game on agrid, in which the computer has selected some cell of the grid, and you have to determine which one.
To do so, Anti Light’s Cell Guessing solution codeforces you will choose someand some cells , and give them to the computer. In response, you will get numbers , where is the manhattan distance from to the hidden cell (so you know which distance corresponds to which of input cells).
After receiving these, you have to be able to determine the hidden cell. What is the smallest for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?
As a reminder, the manhattan distance between cellsand is equal to .
Anti Light’s Cell Guessing solution codeforces Input
The first line of the input contains a single integer( ) — the number of test cases. The description of test cases follows.
The single line of each test case contains two integersand ( ) — the number of rows and the number of columns in the grid.
For each test case print a single integer — the minimumfor that test case.
2 2 3 3 1
Anti Light’s Cell Guessing solution codeforces output
In the first test case, the smallest suchis , for which you can choose, for example, cells and .
Note that you can’t choose cellsand for , as both cells and would give , so we wouldn’t be able to determine which cell is hidden if computer selects one of those.
In the second test case, you should choose, for it you can choose cell or .