ACM-ICPC-OJ训练营

问题 D: Dirt Ratio

时间限制: 18 Sec 内存限制: 128 MB Special Judge
提交: 8 解决: 0
[提交][状态][讨论版][命题人:]

题目描述

In ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed

Xproblems during the contest, and submitted

Y times for these problems, then the ''Dirt Ratio'' is measured as

XY. If the ''Dirt Ratio'' of a team is too low, the team tends to cause more penalty, which is not a good performance.

Picture from MyICPC

Little Q is a coach, he is now staring at the submission list of a team. You can assume all the problems occurred in the list was solved by the team during the contest. Little Q calculated the team's low ''Dirt Ratio'', felt very angry. He wants to have a talk with them. To make the problem more serious, he wants to choose a continuous subsequence of the list, and then calculate the ''Dirt Ratio'' just based on that subsequence.

Please write a program to find such subsequence having the lowest ''Dirt Ratio''.

输入描述

The first line of the input contains an integer

T(1≤T≤15), denoting the number of test cases.

In each test case, there is an integer

n(1≤n≤60000) in the first line, denoting the length of the submission list.

In the next line, there are

n positive integers

a1,a2,...,an(1≤ai≤n), denoting the problem ID of each submission.

输出描述

For each test case, print a single line containing a floating number, denoting the lowest ''Dirt Ratio''. The answer must be printed with an absolute error not greater than

10−4.

样例输入

1
5
1 2 1 2 3

样例输出

0.5000000000

提示

For every problem, you can assume its final submission is accepted.

[提交][状态]