Flu Shot LineupProblem code: FLUSHOT |
All submissions for this problem are available.
A new strain of flu has broken out. Fortunately, a vaccine was developed very quickly and is now being administered to the public. Your local health clinic is administering this vaccine, but the waiting line is very long.
For safety reasons, people are not allowed to stand very close to each other as the flu is not under control yet. However, many people were not aware of this precaution. A health and safety official recently examined the line and has determined that people need to spread out more in the line so that they are at least T units away from each other. This needs to be done as quickly as possible so we need to calculate the minimum distance D such that it is possible for every person to move at most D units so the distance between any two people is at least T. Specifically, D should be the minimum value such that there are locations x'i so that |xi - x'i| ? D for each person i and |x'i - x'j| ? T for any two distinct people i,j. Furthermore, since nobody can move past the receptionist we must also have that x'i ? 0.
The location of each person is given by the number of meters they are standing from the receptionist. When spreading out, people may move either forward or backward in line but nobody may move past the location of the receptionist.
Input
The first line of input contains a single integer K ? 30 indicating the number of test cases to follow. Each test case begins with a line containing an integer N (the number of people) and a floating point value T (the minimum distance that should be between people). The location of each person i is described by single floating point value xi which means person i is xi meters from the receptionist. These values appear in non-decreasing order on the following N lines, one value per line.
Bounds: 1 ? N ? 10,000 and T and every xi is between 0 and 1,000,000 and is given with at most 3 decimals of precision.
Output
For each test case, you should output the minimum value of D with exactly 4 decimals of precision on a single line.
Example
Input: 3 2 4 1 2 2 2 1 2 4 1 0 0.5 0.6 2.75 Output: 2.0000 0.5000 1.4000
Explanation of Sample Data
In the first test case, the first person can move to location 0 and the second to location 4 with the maximum distance moved being 2. In the second case, person 1 can move to location 0.5 and person 2 can move to location 2.5 for a maximum distance moved being 0.5. Finally, in the last output the first person does not move, the second moves to location 1, the third to location 2, and the fourth to location 3. The maximum distance moved by any person was done by the third person who moved 1.4 meters to their destination.
| Author: | friggstad |
| Date Added: | 7-11-2010 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
can a person for example at
can a person for example at location i get a location greater than the location of aperson behind it after spreading
It doesn't make sence, dude.
It doesn't make sence, dude. It will increase D.
can anyone provide some more
can anyone provide some more test cases... i m getting WA.
No, that would be against the
No, that would be against the rules.
@stephen : bt u can atleast
@stephen : bt u can atleast provide some results for some random inputs... .
@ Manohar : No, that would be
@ Manohar : No, that would be against the rules, too. We won't give more testcases just because there are contestants getting WAs.
Can somebody tell what will
Can somebody tell what will be the output if N = 1 and T any be any number
I have mailed the following
I have mailed the following doubt on Jan 1st. No response till now. Can someone give a reply to this
To: feedback@codechef.com
Subject: doubt on FLUSHOT
Date: Sat, 1 Jan 2011 22:29:20 +0530
Hi,
In the problem FLUSHOT,
can there be a case where location of ith indexed person > T*i ?
e.g one of the below mentioned case
5 2
2
3
10
11
13
Here person ( index = 1, value = 3 ) can move to value=4 and person with value = 10 can move backward to 9.
So maximum shift = 1. However few ppl have shifted back & few shifted forward.
Should this case be considered?
The problem says every xi is
The problem says every xi is between 0 and 1,000,000. If there were other restrictions on the locations it would say so.
@madhu - i think the answer
@madhu - i think the answer to your query should be 0.75 as the new positions of ppl could be 1.5, 3.5, 9.25, 11.25,13.25 respectively. anybody, correct me if i am wrong here.
@Myriad,i think final
@Myriad,i think final position should be 1.5, 3.5, 9.5, 11.5 , 13.5 ... so the maximum shift should be 0.5
0.5 is the correct answer for
0.5 is the correct answer for the above example. I miscalculated it.
@Amarjeet and Madhu - thanks
@Amarjeet and Madhu - thanks for the correction :)
How is it possible for a
How is it possible for a solution to take 0M of memory ?
It is given that
It is given that 0<=Xi<=1,000,000 then does it mean that X'i is also within this range after shifting or can people be moved back to any distance....
Can a person stand at a
Can a person stand at a position beyond 1,000,000 after spreading?
The problem statement says
The problem statement says that x'_i >= 0. It doesn't say anything else.
i m facing a very strange
i m facing a very strange problem.... the floating point values are automatically changed. for example if input is 4.9 it becomes 4.900000000254 something like this ., where it must be 4.900000000000000000 ...
<iomanip> is not working ,,,, is there any good site or page for its tutorial. ..any other suggestion is also expected.
@admin There is some bug in
@admin There is some bug in the judge a problem cannot take 0M space
@manohar Try using x/2.0000f etc. in case of computations float varoiables are double by default
@admin: plz tell me why my
@admin: plz tell me why my code is not being accepted... it is an easy prblm with simple trick..its giving me correct ans for any input.... but on submission still it is giving me WA... plz check and tell me one input set for which it fails...
Thanks guddu :)
@manohar....did u get your
@manohar....did u get your sol accepted???...i m having the same problem....plz help!!!
No i dont..
No i dont..
What about output
What about output deviation?
It is said, that "you should output the minimum value of D with exactly 4 decimals of precision on a single line", but it is not said which deviation (relative or absolute) is accepted.
It is common way to give some epsilon (maybe 0.0001), and accept solution if abs(correctAnswer, participantAnswer) < epsilon.
Examples: if correct answer is 0.00005 and I output 0.0001 - will it be accepted? And if I output 0.0000?
I mean abs(correctAnswer -
I mean abs(correctAnswer - participantAnswer) < epsilon in previous message, jast a typo
@burdakov The output must be
@burdakov
The output must be the correct answer rounded off to 4 decimal places.