LVADER - Luke vs. Darth Vader
You know one of the most dangerous villain of all time, it's Darth Vader. It's time to stop him and Master Luke is looking forward to fight against him. They both are in an infinite two-dimensional grid. Each cell is denoted by (x, y). Here x denotes the row number and y denotes the column number of that cell. Please have a look on that picture of 5 * 7 grid to understand.
0, 0 | 0, 1 | 0, 2 | 0, 3 | 0, 4 | 0, 5 | 0, 6 |
1, 0 | ||||||
2, 0 | ||||||
3, 0 | ||||||
4, 0 |
Luke stays at a cell (x1, y1) and Vader stays at another cell (x2, y2). It is guaranteed that x1 <= x2 and y1 <= y2. Master Luke needs to reach Vader’s cell. Each time Luke can move one step below horizontally or vertically or diagonally. That means, if his position is (x, y) then he can move to (x+1, y) or (x, y+1) or (x+1, y+1) cell in a single move. Given Luke and Vader’s position you have to determine in how many ways Luke can reach to the Vader’s cell. As the answer can be very large output the solution modulo 10^9 + 7.
Input
Input starts with an integer (T <= 50) which denotes the number of test case. Each test case consists four integer x1, y1, x2, y2 (0 <= x1 <= x2 <= 100000 and 0 <= y1 <= y2 <= 100000), the position of Luke and Vader.
Output
For each test case, print the number of ways Luke can reach to the Vader’s cell modulo 10^9 + 7.
Example
Input: 3 1 2 2 3 2 2 3 3 3 4 3 5 Output: Case 1: 3 Case 2: 3 Case 3: 1
Explanation
In the first case he can move from (1, 2) to (2, 3) in the following 3 ways:
- (1, 2) → (1, 3) → (2, 3)
- (1, 2) → (2, 2) → (2, 3)
- (1, 2) → (2, 3)
hide comments
Waseem Ahmed:
2021-07-30 03:57:11
TLE? Use closed form of obtaining the Delannoy Number. |
|
yash200:
2017-06-21 16:16:57
just grid concept :) |
|
julkas:
2017-03-22 09:09:32
Theory - https://en.wikipedia.org/wiki/Delannoy_number |
Added by: | Akash |
Date: | 2017-01-25 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Intra KUET programming contest 2016 |