TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

33.3% (2/6)

Description

盩僰麌最近迷上了叫作ニュー・スーパーフックガール的遊戲,但是他常常對他的成績不太滿意,於是他決定採取一種策略來練習這個遊戲裡的每個關卡。

這個遊戲一共有$N$個關卡,由0編號到$N-1$。每一關盩僰麌需要1單位的時間去練習以獲得他想要的成績。他認為分段練習是最好的方法,於是他把這些關卡分成$k$個階段,使得每一段裡的關卡的編號都連續。

盩僰麌對分段練習有獨特的見解,並不只是單純的把每個關卡都刷過一次而已。盩僰麌寫了一個程式,協助他挑選接下來要練習哪一關。
對於每個階段,當這個階段中每一個關卡都練習完了之後,盩僰麌就會練習下一個階段,重複直到每個階段的每個關卡都練習完畢。

而盩僰麌寫的程式的運作方式如下:假設盩僰麌現在練習的階段中,盩僰麌已經練習過的關卡編號是$a_1,a_2,...,a_x$,而還沒練習過且編號最低的關卡編號是$b$,則這個程式會計算出$C=t_b+t_{a_1}+t_{a_2}+\cdots+t_{a_X}$,然後隨機決定它的輸出:$\frac{t_b}{C}$的機率會輸出編號$b$的關卡、$\frac{t_{a_1}}{C}$的機率會輸出編號$a_1$的關卡,以此類推。

不過因為不久後就要舉行這個遊戲的比賽了,請幫盩僰麌算出,如果按照他的這個練習方法,對於每種階段的劃分方法,練習完這個遊戲的期望時間最短可以到多少。

Input Format

第一行有兩個正整數$N, k$,代表的意義如題敘所示。
第二行有$N$個正整數,第$i$個數字代表$t_{i}$。

對於所有的測資,$k \leq N$,$t_{i} \leq 200000$。

子任務(測資)額外限制分數
1(0~11)$N \leq 500, k \leq 3$8
2(0~28)$N \leq 1000, k \leq 5$14
3(0~41)$N \leq 1000, k \leq 1000$32
4(42~54)$N \leq 200000, k \leq 50$56
5(0~72)$N \leq 200000, k \leq 200000$90

Output Format

請輸出一個數字,代表完成所有關卡所需的最少期望時間。
只要輸出的答案與正確答案的絕對誤差或相對誤差不超過$10^ {-4}$(即$\frac{|output-ans|}{max(1,ans)}\leq 10^ {-4}$),那麼將會視為正確。

Sample Input

4 2
100 3 5 7

Sample Output

5.7428571429

Hints

範例測資中,其中一種最好的策略是將第1關分為一段,第2~4關分為第二段,第一段的期望時間為$1$單位時間,第二段的期望時間為$4.7428571429$單位時間,總共為$5.7428571429$,並且沒有別的分段方式能取得更短的總期望時間。

Problem Source

建國中學106學年度校隊補選pB

Subtasks

For Testdata: 0 ~ 11, Score: 8
For Testdata: 0 ~ 28, Score: 14
For Testdata: 0 ~ 41, Score: 32
For Testdata: 42 ~ 54, Score: 56
For Testdata: 0 ~ 72, Score: 90
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1900 131072 65536
1 1900 131072 65536
2 1900 131072 65536
3 1900 131072 65536
4 1900 131072 65536
5 1900 131072 65536
6 1900 131072 65536
7 1900 131072 65536
8 1900 131072 65536
9 1900 131072 65536
10 1900 131072 65536
11 1900 131072 65536
12 1900 131072 65536
13 1900 131072 65536
14 1900 131072 65536
15 1900 131072 65536
16 1900 131072 65536
17 1900 131072 65536
18 1900 131072 65536
19 1900 131072 65536
20 1900 131072 65536
21 1900 131072 65536
22 1900 131072 65536
23 1900 131072 65536
24 1900 131072 65536
25 1900 131072 65536
26 1900 131072 65536
27 1900 131072 65536
28 1900 131072 65536
29 1900 131072 65536
30 1900 131072 65536
31 1900 131072 65536
32 1900 131072 65536
33 1900 131072 65536
34 1900 131072 65536
35 1900 131072 65536
36 1900 131072 65536
37 1900 131072 65536
38 1900 131072 65536
39 1900 131072 65536
40 1900 131072 65536
41 1900 131072 65536
42 1900 131072 65536
43 1900 131072 65536
44 1900 131072 65536
45 1900 131072 65536
46 1900 131072 65536
47 1900 131072 65536
48 1900 131072 65536
49 1900 131072 65536
50 1900 131072 65536
51 1900 131072 65536
52 1900 131072 65536
53 1900 131072 65536
54 1900 131072 65536
55 1900 131072 65536
56 1900 131072 65536
57 1900 131072 65536
58 1900 131072 65536
59 1900 131072 65536
60 1900 131072 65536
61 1900 131072 65536
62 1900 131072 65536
63 1900 131072 65536
64 1900 131072 65536
65 1900 131072 65536
66 1900 131072 65536
67 1900 131072 65536
68 1900 131072 65536
69 1900 131072 65536
70 1900 131072 65536
71 1900 131072 65536
72 1900 131072 65536