A Game With a Sheet of Paper
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Yuuko and Nagi like to play the following game:
Initially they take a checkered sheet of paper of the size of N x M cells. Then, one cell, let's call this cell (X, Y) is marked. Then, they take the moves alternately. A move consists of making a long horizontal or vertical cut. This cut should coincide with one of the lines that divide the sheet into cells. Then, a part that doesn't contain a marked cell is thrown away and another player takes her turn. A player who is unable to make a turn because after the opponent's turn the dimensions of the sheet became equal to 1 x 1 loses. Yuuko plays first.
Yuuko and Nagi have played a lot of games together so now they both know the optimal strategy and always use it. Today girls are going to play a game on a N x M cells sheet of paper, but they haven't yet decided, what is the cell (X, Y) to be marked. Yuuko is interested, in how many ways it's possible to choose this cell so the she can become a winner, regardless of Nagi's moves.
The first line of input consists of an integer T - the number of test cases. Then, T lines describing the test cases follow. The i-th such line contains two integers N and M, separated by a single space.
For each test case, output a single line containing the number of ways to choose the marked cell in order to ensure Yuuko's win.
Input: 2 5 8 6 7 Output: 40 42
T = 100, 1 <= N, M <= 10 : 25 points.
T = 100, 1 <= N, M <= 1000 : 36 points.
T = 100, 1 <= N, M <= 106 : 39 points.
|Tags||easy, ltime10, nim, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.