Problem of the day
.
Input: ‘L’ = 8, ‘B’ = 10, ‘N’ = 1, ‘POS’ = {4}, ‘R’ = {5}
Output: -1
In this case,
As shown in the figure above, even if we fix the only street light of the city, the whole city area can’t be covered. Hence the output is ‘-1’.
The first line will contain the integer ‘T’, the number of test cases.
Each test case consists of three lines.
The first line of input contains three integers, ‘L’, ‘B’, and ‘N’ separated by spaces.
The next line contains space-separated ‘N’ non-negative distinct integers, denoting the positions of the street lights in the city.
And the last line contains space-separated ‘N’ non-negative integers, denoting the radius of luminance of street lights in the city.
For each test case, print the minimum number of street lights required to illuminate the whole city with new street lights or print ‘-1’ if it is impossible to do so.
You don't need to print anything. It has already been taken care of. Just implement the given function.
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
‘N’ <= ‘L’ <= 10^5
1 <= ‘B’ <= 10^4
0 <= ‘POS[i]’ <= ‘L’
All ‘POS[i]’ are distinct, i.e. ‘POS[i] != POS[j]’ holds true for all ‘i != j’ such that ‘1’ <= ‘i’ <= ‘N’ and ‘1’ <= ‘j’ <= ‘N’
0 <= ‘R[i]’ <= 10^4
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
2
6 6 3
6 1 4
1 0 5
10 4 2
2 7
1 1
1
-1
For the first test case,
It is clearly visible, that it is advantageous to fix only the street light at position ‘4’.
Hence, the output will be: 1
For the second test case,
It is clearly visible, that even if we fix all the street lights of the city, we can’t have the luminance of new street lights in the whole city. Hence the output is ‘-1’
Hence, the output will be: -1
2
20 6 4
1 8 13 20
5 5 5 5
5 1 5
0 1 2 3 5
0 0 0 0 1
4
-1