TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

96.9% (31/32)

Submission's AC Ratio

48.8% (63/129)

Description

你,身為一個蘿莉控,身邊當然會有許多蘿莉,其中恰有一個蘿莉是SS級的蘿莉。你原本不知情,直到農曆新年放鞭炮時,SS級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲,你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫,所以你為了要找出哪隻蘿莉是SS級的蘿莉而買了許多鞭炮。
為了省鞭炮,你將蘿莉們編號為$0$到$n-1$。你每次都可以選一些蘿莉和你進入一個隔音間。 當然,直接撲下去好像還不錯,不過請記住你現在的目標。 進入隔音間後,你就點燃鞭炮。如果SS級的蘿莉也在隔音間,你就會聽到那個令人精神振奮的叫聲;如果沒有,你就只會聽到鞭炮聲。你的目標是使用最少的鞭炮找出SS級的蘿莉。
另外,你其實早就調查了每個蘿莉是SS級的機率,並以陣列$P[0],\cdots,P[n-1]$記錄,代表第$i$隻蘿莉是SS級的機率是$\dfrac{P[i]}{\sum_{j=0}^ {n-1}P[j]}$。請問,若你使用最佳的策略尋找SS級的蘿莉,所花費的鞭炮數的期望值$X$是多少?

($\sum_{j=0}^ {n-1}P[j]$代表$P[0] + P[1] + \cdots + P[n - 1]$。期望值=$\sum$(某事件發生機率)$\times$(某事件發生時需要幾個鞭炮))

Input Format

第一行有一個正整數$n\leq 10^ 6$ 代表蘿莉的數量,
接著第二行會有$n$個正整數,分別代表$P[0],\cdots,P[n-1]$,其中$P[i]\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~4) $P[i]=1$ 9
2 (5~9) $n\leq 10$ 13
3 (10~14) $n\leq 17$ 15
4 (15~19) 63

Output Format

為了方便,請輸出$X\times\sum_{i=0}^ {n-1}P[i] $。

Sample Input

4
1 1 2 3

Sample Output

13

Hints

註:
先把編號3的蘿莉帶到小房間獨處,
1. 如果聽到叫聲,就找到了。
2. 如果沒有,再把編號0跟1的蘿莉帶到小房間:
2-1. 如果聽到叫聲,把編號1的蘿莉趕出小房間再試一次,就知道到底是0號還是1號了。
2-2. 如果沒有,結果就是2號。
使用的鞭炮數的期望值是13/7。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校隊選拔:初試pF

Subtasks

For Testdata: 0 ~ 4, Score: 9
For Testdata: 5 ~ 9, Score: 13
For Testdata: 10 ~ 14, Score: 15
For Testdata: 15 ~ 19, Score: 63
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536