All submissions for this problem are available.
A traveler has to travel from a source to a destination along a straight path,the locations of which are given as s1 and d1. On his way he encounters N townships each consisting of any no of houses, all located along the straight path,the locations of which are given by t1,t2,.....tk.
Each township must have at least a single house and no house can be in more than 1 township.The source and destination are not in any township.The traveler must stop in every township.Again,he also must stop in only a single house in a township.The traveler can stop in a house depending on whether that house is reachable from the house he stayed in the previous township,(i.e the maximum distance M the traveler is allowed to travel before resting will be specified).
More over he cannot stay in any house which is not included in any township. You have to find the no of ways to reach the destination from the source.
Assume that all the houses in the first township are reachable from the source and the destination is reachable from all the houses in the last township irrespective of the value of M.
The first line contains the number of test cases T
For each test case, the first line contains two space separated integers A and M. A is the total no of houses including source and destination and M is the maximum distance the traveler is allowed to travel before resting.
Then A lines will follow and the ith line will have the value of ti. The input will be such that a solution will always exist.The locations will be given in ascending order.
Then the next line will contain the number of townships N. Then N lines follow with each line specifying the starting and ending index of the houses located in that township given in ascending order(i.e the indexes of the array where the house locations are stored.Index position is assumed to start from 0).
Output in a new line the no of possible ways to reach from source to destination..
For two consecutive test cases, the outputs should have a gap of one line between them.
- 2 < A <= 1000
- 1 <= M <= 500
- s1 < t1 < t2 < ....... < tk < d1
- 1 <= N <= A-2
- 0 <= ti <= 5000
Starting index of a house in a township, a > Ending index of a house in that township, b
Distance between the end houses in two consecutive townships,
D >= M
Distance between the starting houses in two consecutive townships,L <= M
The source must be reachable to all the houses in the first township
All houses in the last township must be reachable to the destination
1 8 3 0 2 3 4 6 8 9 11 3 2 2 4 4 5 6Output:
Example case 1.
Here the two paths are
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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