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