TopCoder

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

User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

11.3% (17/150)

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$,並且沒有別的分段方式能取得更短的總期望時間。

2018/03/20 測資加強。

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)
0 1900 131072
1 1900 131072
2 1900 131072
3 1900 131072
4 1900 131072
5 1900 131072
6 1900 131072
7 1900 131072
8 1900 131072
9 1900 131072
10 1900 131072
11 1900 131072
12 1900 131072
13 1900 131072
14 1900 131072
15 1900 131072
16 1900 131072
17 1900 131072
18 1900 131072
19 1900 131072
20 1900 131072
21 1900 131072
22 1900 131072
23 1900 131072
24 1900 131072
25 1900 131072
26 1900 131072
27 1900 131072
28 1900 131072
29 1900 131072
30 1900 131072
31 1900 131072
32 1900 131072
33 1900 131072
34 1900 131072
35 1900 131072
36 1900 131072
37 1900 131072
38 1900 131072
39 1900 131072
40 1900 131072
41 1900 131072
42 1900 131072
43 1900 131072
44 1900 131072
45 1900 131072
46 1900 131072
47 1900 131072
48 1900 131072
49 1900 131072
50 1900 131072
51 1900 131072
52 1900 131072
53 1900 131072
54 1900 131072
55 1900 131072
56 1900 131072
57 1900 131072
58 1900 131072
59 1900 131072
60 1900 131072
61 1900 131072
62 1900 131072
63 1900 131072
64 1900 131072
65 1900 131072
66 1900 131072
67 1900 131072
68 1900 131072
69 1900 131072
70 1900 131072
71 1900 131072
72 1900 131072