TopCoder

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

User's AC Ratio

96.9% (63/65)

Submission's AC Ratio

38.9% (105/270)

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

No. Testdata Range Score
1 0~4 9
2 5~9 13
3 10~14 15
4 15~19 63

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4