盩僰麌最近迷上了叫作ニュー・スーパーフックガール的遊戲,但是他常常對他的成績不太滿意,於是他決定採取一種策略來練習這個遊戲裡的每個關卡。
這個遊戲一共有$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$的關卡,以此類推。
不過因為不久後就要舉行這個遊戲的比賽了,請幫盩僰麌算出,如果按照他的這個練習方法,對於每種階段的劃分方法,練習完這個遊戲的期望時間最短可以到多少。
第一行有兩個正整數$N, k$,代表的意義如題敘所示。
第二行有$N$個正整數,第$i$個數字代表$t_{i}$。
對於所有的測資,$k \leq N$,$t_{i} \leq 200000$。
請輸出一個數字,代表完成所有關卡所需的最少期望時間。
只要輸出的答案與正確答案的絕對誤差或相對誤差不超過$10^ {-4}$(即$\frac{|output-ans|}{max(1,ans)}\leq 10^ {-4}$),那麼將會視為正確。
範例測資中,其中一種最好的策略是將第1關分為一段,第2~4關分為第二段,第一段的期望時間為$1$單位時間,第二段的期望時間為$4.7428571429$單位時間,總共為$5.7428571429$,並且沒有別的分段方式能取得更短的總期望時間。
2018/03/20 測資加強。
建國中學106學年度校隊補選pB
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~11 | $N \leq 500, k \leq 3$ | 8 |
2 | 0~28 | $N \leq 1000, k \leq 5$ | 14 |
3 | 0~39, 41 | $N \leq 1000, k \leq 1000$ | 32 |
4 | 40, 42~54 | $N \leq 200000, k \leq 50$ | 56 |
5 | 0~72 | $N \leq 200000, k \leq 200000$ | 90 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 |