TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

79.2% (19/24)

Description

如果你沒有玩過皮卡恩打桌球,至少你也要玩過卡恩歷險記;
如果你沒有玩過卡恩歷險記,至少你也要把這題給AC!

不妨假設你是個很威的電玩人物卡恩,
目前經過一番激烈的戰鬥,砍殺了無數隻怪物,你有若k點技能點可供使用
而你有n項不同的技能(好威桌球殺球、瞬間秒殺法、小品演算法……),分別編號為s1、s2、s3、…、sn。

我們可以把你的技能分布畫成圖。
做圖方法是以一個中心畫出n條線,相鄰兩條之間的夾角相同。
而每條線就代表一項技能,這些線依順時針順序是L1, L2, …, Ln
而我們依照si的點數在Li上面做點Pi,且Pi到中心的距離就是si之點數。
將所有點Pi依序連起來,得到一個多邊形P,定義你這個人物的「強度」,就是P的面積。
(敘述十分難懂,可以可參考一下上圖。圖中強度就是陰影部分的面積。注意到s1和s5是相鄰的)

現給定n、k,以及目前各個技能的點數依序為s1、s2、s3、…、sn
試求將k點技能點使用在這n項技能上後,你的強度最多可以變成原來的多少倍?(可假設技能是沒有上限的!)

當然,一點技能點可以使一項技能等級增加1
而你並不能將一點技能點拆開來用,例如用在A技能0.4,用在B技能0.6
我想這些常識不必多提

請輸出到小數後第四位

Input Format

第一行有一個整數t,代表有幾組測資
每組的第一行有兩個整數n和k,依序代表有幾項技能、以及可供使用的技能點
接下來一行有n個數,代表每項技能目前的點數

技能數目4<=n<=100,000
可用技能點數0<=k<=5,000,000
目前點數1<=si<=5,000,000

Output Format

請輸出一個小數,四捨五入至小數點後四位,代表最多可以變為原先強度的多少倍?

Sample Input

1

6 4
2 2 2 3 1 3

Sample Output

1.9231

Hints

2019/03/31 測資修正

Problem Source

原TIOJ1319 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 65536 1
1 1500 65536 65536 2
2 1500 65536 65536 3
3 1500 65536 65536 4
4 1500 65536 65536 5
5 1500 65536 65536 6
6 1500 65536 65536 7
7 1500 65536 65536 8
8 1500 65536 65536 9
9 1500 65536 65536 10
10 1500 65536 65536 11
11 1500 65536 65536 12