Submit | All submissions | Best solutions | Back to list |
NSITACMD - Save the girlfriend |
Archit needs to save his girlfriend from the evil vampire. He is in Room 1 and his girlfriend is captured in Room N. He also knows the distance between each room and the girlfriend's room. He has decided only to move in such a way that he gets strictly nearer to his destination (absolute distance). Formally, he moves to a room which is nearer to room N at each step.
There are several tunnels that connect some of the rooms. A tunnel can be used in a bi-directional way.
Help him find out the number of ways by which he could reach the Nth room and save his girlfriend.
If it is impossible for him to save his girlfriend, output "impossible" (without the quotes.)
Input
First line denotes the number of test cases T (<= 50).
Each test case begins with a single integer N (1 < N <= 1000).
Then follows N space separated integers (D[i]) denoting the distance between Room i and Room N. (D[i] <= 10000)
The following N lines contain N space separated integers each.(F[i][j])
The jth column on ith row is 1 if there exists a tunnel between Room i and Room j and 0 otherwise.
Note that F[i][j] = F[j][i] because of bidirectional tunnels.
and D[N] = 0
Output
Output the number of ways for him to reach the Nth Room or "impossible" otherwise.
Since, the results can be very large output the number of ways modulo 124027.
Example
Input: 1 4 9 3 5 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 Output: 2
Added by: | Mukul Gupta |
Date: | 2013-03-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C C++ 4.3.2 CPP C99 JAVA |
Public source code since: | 2013-03-14 00:00:00 |
hide comments
2013-03-14 17:32:50 Archit Goel
So, I along with my team finally saved my girlfriend. :P |
|
2013-03-14 16:48:46 dhruvbansal
@abhishek lol seems tough to save goel's girlfriend..:D |
|
2013-03-14 16:33:16 Abhishek Mishra
archit goel....;) |
|
2013-03-14 15:53:51 Mukul Gupta
There are two paths for the sample input test case. Path 1: 1->2->4 Path 2: 1->3->2->4 You can verify that distance to the Nth room strictly decreases with every move. |
|
2013-03-14 15:48:01 Rishul Aggarwal
op explanation pls!! |