ITRIX_E - THE BLACK AND WHITE QUEENS

no tags 

Subru and Shanmu are playing Chess. Shanmu wonder about queens. So he asked Subru the following question

How many ways are there to place a black and a white Queen on an M × N chessboard such that they do not attack each other? The queen can be moved any number of unoccupied squares in a straight line vertically, horizontally, or diagonally.

Subru gave the answer in seconds for a given chess board of size M × N (M <= N). Can you repeat the same with your code?

Input Format:

The first line contains the integer “t” which indicates the number  of test cases. Each of the following t lines contains two integers M and N separated by spaces (M<=N).

Output Format:

Output for each case consists of one line: The number of ways of placing a black and a white queen on a M × N chess board such that they do not attack each other.

Constraints: T <= 10000, 2 <= M <=10^10, 2 <= N <= 10^10. And M<=N.

Sample Input:

3

5 5

3 4

2 2

Sample Output:

280

40

0


hide comments
Francky: 2020-01-23 00:50:36

Warning, with some cases you'll have M > N, others with M <= N.

nadstratosfer: 2020-01-21 23:17:21

I suck at these problems, but like a lemming that doesn't die, just keeps falling off the cliff, I keep getting into them over and over again, thinking it'd be easy, then spending hours staring at my own analysis as if it was written in Etruscan. Then I go grab something from the fridge and out of the blue I get the idea that gets me to AC. So I never learn how to arrive at the solution in an orderly manner and next time I encounter "how many ways.." it's bound to cost me a whole evening. Again!

Sushovan Sen, your result is correct but int64 is not enough for bigger cases.

Sushovan Sen: 2016-04-14 11:34:47

Is long long in C is enough?
Can you please check submission id : 16739788

Or at least few other test cases.
what is op for
1
21202 35487

566030597842239020 ??

@nadstratosfer thanks.
It was naive of me to ask the question after figuring out the formula. AC now

Last edit: 2022-06-03 12:00:14

Added by:Radhakrishnan Venkataramani
Date:2011-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ITRIX 2011