TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

92.3% (84/91)

Submission's AC Ratio

44.1% (143/324)

Tags

Description

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

j=0n1P[j]代表P[0]+P[1]++P[n1]。期望值=(某事件發生機率)×(某事件發生時需要幾個鞭炮))

Input Format

第一行有一個正整數n106 代表蘿莉的數量,
接著第二行會有n個正整數,分別代表P[0],,P[n1],其中P[i]109

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

Output Format

為了方便,請輸出X×i=0n1P[i]

Sample Input 1

4
1 1 2 3

Sample Output 1

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 (VSS, 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