z-radar2
You have a straight border line which is covered with N radars.All of the radars have the same distance of sight, and are positioned along the line.There are always radars at the beginning and the end of the border line. The first and the last radar are not movable.Your task is to minimize the power the radars use, by minimizing the maximum distance between any two adjacent radars.
The radars can be moved in either direction along the line, but the movement costs money, and you are allowed to move the radars only K kilometer in total.
Radars can be moved only by full kilometer.
Example.
The line has length of 12.The radars are initially positioned at points 2, 6, 8.
The money is allowing the radars to be moved 3km in total. As there are radars at points 0 and 12. (there are always radars at the beginning and the end of the line), by arranging the radars at positions 3, 6, 9, we can cover the whole line, with a minimal distance of the radars to be 3 kilometers. For this arrangement we would need to move the radar1 for 1km and radar3 for 1km, resulting in total move of 2km.
If the money would allowed for only 1km to be moved, the solution would be 2, 6, 8, which would result in minimal distance of 4km.
-the first and the last radar always exist and are not passed as arguments in input
-two or more radars can be on the same place.
-additional radars may exist on the beginning or the end of the border line.
Explanation: There are four possibilities to minimize the maximum distance in the third example. We can move the radar at position 94 for 3 kilometers, or move the radar at 53 for 3 kilometers, or we can move both for 1 and 2 kilometers.
The radars can be moved in either direction along the line, but the movement costs money, and you are allowed to move the radars only K kilometer in total.
Radars can be moved only by full kilometer.
Example.
The line has length of 12.The radars are initially positioned at points 2, 6, 8.
The money is allowing the radars to be moved 3km in total. As there are radars at points 0 and 12. (there are always radars at the beginning and the end of the line), by arranging the radars at positions 3, 6, 9, we can cover the whole line, with a minimal distance of the radars to be 3 kilometers. For this arrangement we would need to move the radar1 for 1km and radar3 for 1km, resulting in total move of 2km.
If the money would allowed for only 1km to be moved, the solution would be 2, 6, 8, which would result in minimal distance of 4km.
-the first and the last radar always exist and are not passed as arguments in input
-two or more radars can be on the same place.
-additional radars may exist on the beginning or the end of the border line.
Input The first line will contain the numbers N,M and K. N represents the number of radars(1<=N<=50) ,M is the length of the border line in kilometers(1<=M<=100), and K is the total kilometers allowed for the radars to be moved ( 0<=K<=100000).
From the next N lines read the positions of the radars. This numbers will be between 0 and M inclusive.
From the next N lines read the positions of the radars. This numbers will be between 0 and M inclusive.
OutputOutput the minimal distance between radars after their rearranging
Input
Output
3 12 3
2
6
8Output
3Input
Output
3 12 1
2
6
8Output
4Input
Output
6 99 3
48
11
53
41
94
47Output
38Explanation: There are four possibilities to minimize the maximum distance in the third example. We can move the radar at position 94 for 3 kilometers, or move the radar at 53 for 3 kilometers, or we can move both for 1 and 2 kilometers.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.