PONY3 - Discords Dilemma

Discord is in trouble for causing discord, so he is trying to escape from Equestria. He's arrived at the port, and he doesn't care what boat he gets on, he just wants to get out. He can see the boat schedule, where he sees that N boats are arriving today,

boat 1 arrives any time within a_1 minutes

boat 2 arrives any time within a_2 minutes

...

boat N arrives any time within a_N minutes (uniform distribution)

Tell discord the expected number of minutes he needs to wait for a boat to arrive.

For some reason, you should be accurate to 10^-6 of a minute.

Input Format:

T (number of test cases)

N1 (number of boats for test case 1)

a1 a2 ... aN

N2

...

NT

...

Output Format:

answer1

answer2

...

answerT

Limits:

1 <= T <= 100

1 <= N <= 100

1 <= ai <= 1000

Also, N * max{ai} <= 10000

Sample Input:
4
1
5
3
49 50 51
3
50 50 50
3
2 7 19

Sample Output:
2.500000
12.495000
12.500000
0.874687
Note: Round however Java would round if you used the statement System.out.printf("%.6f\n", answer);

Added by:Alex Anderson
Date:2012-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-01-08 22:35:43 (Tjandra Satria Gunawan)(曾毅昆)
finally 0.00s ;-) computed in O(1) time...
2012-03-15 12:51:28 Mitch Schwartz
Hm, I suspected precision issues, but when comparing between my C solutions and Python with Fraction, I get matching results for randomly generated data. I also tried putting a tweak to force printf to give half up rounding rather than half even. Also did sanity checks with simulations. Any hint about how my code fails? My latest C submission has ID 6658751. Thanks.

EDIT: I've looked at the testcases, it seems that the method you use to solve it is correct, but introduces precision errors more rapidly. The cases that you fail all tend to have N >= 55, and some of them return negative results. (Also, clarified the rounding rule)

Reply (Mitch): Thanks a lot for the reply. Now I noticed I missed test cases such as

100
1 1 1 ... 1

Looks like I'll need to find a better way.

Last edit: 2012-03-15 14:08:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.