TopCoder

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

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

35.7% (5/14)

Tags

Description

「完…完成了!」
小向畫完了魔法陣,而紅色果實也隨之消失。魔力也漸漸回到了小向以及希爾伯特身體。然而……
「太慢了喲,小向。」
不知不覺間,小向、希爾伯特以及小向的師父上出現了一個巨大的魔法陣。

「在你慢慢吞吞的時候,我已經構築好了如~此大的魔法陣喲。這個魔法陣就是我的最終目的:他會把你們兩個的魔力轉移到我的身上,我就會成為不可一世的大魔導士了喲!」
露出真面目的師父講話變得愈來愈噁心了。

不過這個魔法陣還沒構築完全,小向的師父仍然在傾注全力構築魔法陣。看來只要攻擊術者,魔法陣便會消失,小向如此想道。於是,小向衝到了師父身邊,試圖使出近身攻擊魔法。沒想到小向的師父周遭突然出現了光牆。

「你以為我為毫無防備嗎?太天真了喲!」

話雖如此,小向一眼識破了,這是市售的防禦用魔法道具。看來為了構築魔法陣,師父也無暇挪出多餘的精力以及魔力防禦了。

市售的防禦用魔法道具共有$N$種模式。為了避免敵人深入解析術式進而破壞道具,這個魔法道具建出的光牆每被攻擊一次就會隨機切換模式(也有可能不切換)並反彈傷害。具體地說,每被攻擊一次後,魔法道具的$N$種模式出現的機率都一樣。小向雖然對這個魔法道具有一定的認識,但她也沒有十足的把握一定能破解魔法道具的光牆。具體來講,對於$N$種模式,小向破解光牆的機率分別是$P_0,P_1,\dots,P_{N-1}$。如果成功破解了,那麼小向就能攻擊師父消除魔法陣。如果失敗了,光牆就會隨機進入$N$種模式中的其中一種。而小向還留有嘗試破解$K$次的魔力。如果嘗試了$K$次之後小向仍然沒成功,那麼就只有死路一條了。

聰明的小向當然看得出來當前光牆的模式是哪一個模式。不過破解光牆的機率有高有低,如果遇到破解機率太低的光牆,小向當然希望光牆重新切換模式。在這種情況下,小向可以選擇攻擊光牆使得光牆切換模式(當然也有可能不切換)。不過如果攻擊不當,就會被光牆反彈的傷害波及,倒地不起。攻擊光牆而不被波擊的成功機率和小向所剩下的魔力有關係。具體地說,如果小向還有$i$次嘗試的魔力,那麼成功機率便是$\frac{i}{K+1}$ 。請注意:如果小向失敗的話,她就不能再進行任何嘗試,也就是說只有死路一條了。不過背著如此風險當然也會有相對應的收穫。如果成功的話,小向會從光牆反彈的魔力中多獲得$U$次嘗試的魔力。然而,不論如何,小向最多只能保有嘗試$K$次的魔力,多出來的魔力便會消散在大氣中。

聰明的小向當然希望採取最佳的策略,在適當的時機讓光牆切換模式。請你幫忙小向找出最佳的策略。方便起見,你只需要計算最佳策略下小向成功破解光牆的機率。

Input Format

第一行有兩個正整數$N\leq 10^ 5, K\leq 500$以及一個非負整數$U\leq 500$,分別代表光牆的模式種類數、小向還有的魔力以及小向攻擊光牆後能從光牆獲取的魔力。
第二行有$N$個0到1之間的數$P_0,\dots,P_{N-1}$,代表小向成功破解$N$種模式的光牆的機率。這$N$個數是小數點後有九位的小數。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 3,K\leq 10,U=0$ 4
2 (5~9) $N\leq 3000,K\leq 10, U=0$ 12
3 (10~14) $K\leq 10,U=0$ 16
4 (15~19) $N\leq 3, K\leq 3$ 8
5 (20~24) $N\leq 100, K\leq 3$ 16
6 (25~29) $K\leq 10$ 20
7 (30~34) 24

Output Format

請輸出一個數,代表最佳策略下小向成功破解光牆的機率。只要絕對誤差不超過$10^ {-9}$都視為正確。

Sample Input

2 2 0
0.000000000 1.000000000

Sample Output

0.800000000

Hints

範例測資中,最佳策略為:第一次嘗試不論遇到哪種光牆都嘗試。第二次嘗試如果遇到破解機率為0的光牆就攻擊光牆,否則就嘗試。

Problem Source

Problem Set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~4 4
2 5~9 12
3 10~14 16
4 15~19 8
5 20~24 16
6 25~29 20
7 30~34 24

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4
20 1000 65536 262144 5
21 1000 65536 262144 5
22 1000 65536 262144 5
23 1000 65536 262144 5
24 1000 65536 262144 5
25 1000 65536 262144 6
26 1000 65536 262144 6
27 1000 65536 262144 6
28 1000 65536 262144 6
29 1000 65536 262144 6
30 1000 65536 262144 7
31 1000 65536 262144 7
32 1000 65536 262144 7
33 1000 65536 262144 7
34 1000 65536 262144 7