TopCoder

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

26.4% (14/53)

Description

你,身為一個蘿莉控,身邊當然會有許多蘿莉,其中恰有一個蘿莉是SS級的蘿莉。你原本不知情,直到農曆新年放鞭炮時,SS級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲,你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫,所以你為了要找出哪隻蘿莉是SS級的蘿莉而買了許多鞭炮。
為了省鞭炮,你將蘿莉們編號為$0$到$n-1$,依序從你的右邊開始往右排。每次放鞭炮時,你都可以控制音量,使得所有編號小於等於$k$的蘿莉都聽到了鞭炮聲($0 \leq k \leq 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$是多少?

覺得似曾相識嗎?我也這麼覺得。但是你覺得我會那麼好心嗎?

Input Format

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

子任務(測資) 額外限制 分數
1 (0~1) $P[i]=1$ 5
2 (2~4) $n\leq 18$ 7
3 (2~7) $n \leq 800$ 10
4 (2~10) $n \leq 4000$ 13
5 (2~13) $n \leq 10^ 4$ 21
6 (0~19) 無限制 44

Output Format

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

Sample Input

5
2 1 1 1 1

Sample Output

14

Hints

對於範例測資的兩種解法:

一、先取$k=2$:
1. 如果聽到叫聲,就再取$k=0$:
1-1. 如果聽到叫聲,就找到了。
1-2. 如果沒有,取$k=1$就可以知道了。
2. 如果沒有,就再取$k=3$就可以知道了。
使用的鞭炮數的期望值是14/6。

二、也可以先取$k=0$:
1.如果聽到叫聲,就找到了。
2.如果沒有,就再取$k=2$:
2-1.如果聽到叫聲,就再取$k=1$就可以知道了。
2-2.如果沒有,就再取$k=3$就可以知道了。
使用的鞭炮數的期望值還是14/6。

Problem Source

Description by Paupière
Problem set by Yihda Yol
建國中學105學年度校內第五次模擬賽pC

Subtasks

No. Testdata Range Score
1 0~1 5
2 2~4 7
3 2~7 10
4 2~10 13
5 2~13 21
6 0~19 44

Testdata and Limits

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