Logan and his MATRIX game
All submissions for this problem are available.
Charles: "She can learn to be BETTER."
Logan: "Better than me??"
Charles: "Actually, YES!!"
Charles wants Logan to train Laura, and Logan reluctantly agrees.
The rows are defined in top to bottom order, and the columns are defined in left to right order
Logan provides Laura coordinates of 2 rectangular sub-grids.
First of all, Laura must ignore the common area of both the rectangular sub-grids.
Logan doesn't stop at this, as he wants Laura to be the best.
The steps must be taken in such a way that at each instant she stays in the park only.
Laura needs to tell the distinct number of ways to achieve the required goal.
Two ways are considered to be different if they have atleast one different step.
As the number of ways can be very large, print the answer modulo 109+7
Note: Large I/O Files. Use Fast I/O like scanf/printf for C++
First line contains 2 integers - R and C denoting the dimensions of the matrix M
R lines follow, with each line comprising C integers.
Next line contains integer K- denoting the number of tasks to be performed .
K lines follow.
Each of the K lines has 8 integers- R1, C1, R2, C2, R3, C3, R4, C4 - such that first four integers are co-ordinates of first rectangular sub-grid. (R1,C1 ) denotes the top left corner, and (R2,C2) denotes the bottom right corner of the rectangular sub-grid 1. and next four integers are co-ordinates of second rectangular sub-grid. (R3,C3 ) denotes the top left corner, and (R4,C4) denotes the bottom right corner of the rectangular sub-grid 2.
Next line contains integer T - dimension of square matrix N
Next line contains integer Z- the number of queries to be answered.
Z lines follow.
Each of the next Z lines has 2 integers - A and B denoting the starting coordinate
For each of the Z queries, print the required number of ways as described. For each query, answer must be on the separate line.
- 1 ≤ R,C ≤ 1000
- 1 ≤ M(i,j) ≤ 109
- 1 ≤ K ≤ 20000
- 1 ≤ R1 ≤ R2 ≤ R
- 1 ≤ R3 ≤ R4 ≤ R
- 1 ≤ C1 ≤ C2 ≤ C
- 1 ≤ C3 ≤ C4 ≤ C
- Both the rectangular subgrids are not exactly same
- 1 ≤ T ≤ 20
- 1 ≤ Z ≤ 400
- 1 ≤ A,B ≤ T
1 1 3
1 6 1
8 1 1
1 1 2 2 2 2 3 3
The rectangular grid can be shown as above.
Blue colored region denotes first sub-grid, and red colored region denotes second sub-grid
After eliminating the overlapping region, we see than Min=1 and Max=1
In the square grid of size 3, starting point is (1,1)
There are 64 different ways in which Laura can move 2 steps from cell (1,1).
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions