Problem 3

All submissions for this problem are available.
A lame knight is located at the bottomleft corner of a height(H) x width(W) chessboard.
Unlike a healthy knight, a lame knight can only make moves where he goes to the right.
The only possible moves are:
1. 2 cells up, 1 cell right;
2. 1 cell up, 2 cells right;
3. 1 cell down, 2 cells right;
4. 2 cells down, 1 cell right.
The knight will make one trip, and he wants to maximize the number of visited cells.
The knight's starting cell counts toward this number. There is also one restriction for the knight's trip:
it must contain each kind of a move at least once, unless it is shorter than 4 moves.
If the knight makes less than 4 moves (thus visiting less than 5 cells), his moves are not limited in any way.
Input
The first line of input will consist of the number of test cases t(1<= t <=20) followed by t test cases.
Each test case will contain an integer height H(1<=H<=2,000,000,000) and width W(1<=W<=2,000,000,000)
all seperated by spaces
OutPut
Output is an integer giving the maximal number of cells the knight can visit during one trip on a H x W chessboard.
Examples
Input 5 100 50 1 1 17 5 2 4 20 4 OutPut: 48 1 4 2 4 For the first test case there are 1 move of kind 2, 1 move of kind 3, 23 moves of kind 1 and 22 moves of kind 4 (Other than the first state so 1 is always there). For the second test case there are no possible moves, so the only visited cell is the starting cell. For the third test case it's possible to visit 5 cells (making 4 moves of kind 1 for example), but it's impossible to make it by 4 different moves. So, the best strategy here is to make 3 moves (thus visiting 4 cells). For the fifth test case there are 4 cells that can be visited using 2 moves of kind 1 and 1 move of kind 4.
Author:  admin 
Tags  admin 
Date Added:  21092009 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 