1613 . 尋找蘿莉
TopCoder
Tags
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 1
1 1 2 3
Sample Output 1
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 |