TopCoder

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

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

36.1% (61/169)

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$是多少?

覺得似曾相識嗎?我也這麼覺得。不過要是解法跟你現在想的那樣一樣,那為什麼這題滿分是破表的150呢?

Input Format

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

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

最後一個子任務為加分題。
對於該子任務,$n \leq 800$的限制不再適用。

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

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

Subtasks

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