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

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 8
For Testdata: 2 ~ 2, Score: 8
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 8
For Testdata: 5 ~ 5, Score: 8
For Testdata: 6 ~ 6, Score: 8
For Testdata: 7 ~ 7, Score: 8
For Testdata: 8 ~ 8, Score: 8
For Testdata: 9 ~ 9, Score: 8
For Testdata: 10 ~ 10, Score: 8
For Testdata: 11 ~ 11, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 65536
1 1500 65536 65536
2 1500 65536 65536
3 1500 65536 65536
4 1500 65536 65536
5 1500 65536 65536
6 1500 65536 65536
7 1500 65536 65536
8 1500 65536 65536
9 1500 65536 65536
10 1500 65536 65536
11 1500 65536 65536