TopCoder

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

User's AC Ratio

90.3% (28/31)

Submission's AC Ratio

40.9% (81/198)

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

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

Testdata and Limits

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