Problem I
Wood Cutting
Languages
en
ja
Yraglac recently decided to get into the wood cutting business, and now has $N$ customers who would like to have their wood cut. A piece of wood of size $s$ takes $s$ time units to cut, and Yraglac can only cut a single piece of wood at a time. To maximize customer happiness, Yraglac would like to minimize the average total time a customer has to wait to have all of their wood pieces cut. Can you help him?
Input
The first line contains a single integer $T \leq 10$ giving the number of test cases. Each test case begins with an integer $N$ ($1\leq N \leq 10^5$), the number of customers. $N$ lines follow, where the $i$th line begins with an integer $W_ i$ ($1 \leq W_ i \leq 10^5$), the number of wood pieces that customer $i$ would like to have cut, followed by $W_ i$ integers, the sizes of the wood pieces of the customer. Each wood piece has a size between $1$ and $1\, 000$ inclusive. The total number of wood pieces will not exceed $10^5$.
Output
For each test case, output a single line containing the minimum average total time a customer will wait to have all of their wood pieces cut. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
2 1 2 7 5 2 1 7 1 5 |
12.0000000000 8.5000000000 |