TopCoder

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

User's AC Ratio

76.9% (40/52)

Submission's AC Ratio

34.2% (100/292)

Tags

Description

你,身為一個蘿莉控,身邊當然會有許多蘿莉,其中恰有一個蘿莉是SS級的蘿莉。你原本不知情,直到農曆新年放鞭炮時,SS級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲,你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫,所以你為了要找出哪隻蘿莉是SS級的蘿莉而買了許多鞭炮。
為了省鞭炮,你將蘿莉們編號為0n1,依序從你的右邊開始往右排。每次放鞭炮時,你都可以控制音量,使得所有編號小於等於k的蘿莉都聽到了鞭炮聲(0kn1),剩下的蘿莉都沒有聽到鞭炮聲。如果SS級的蘿莉聽到了鞭炮聲,你就會聽到那個令人精神振奮的叫聲;如果沒有,你就只會聽到鞭炮聲。你的目標是使用最少的鞭炮找出SS級的蘿莉。
另外,你其實早就調查了每個蘿莉是SS級的機率,並以陣列P[0],,P[n1]記錄,代表第i隻蘿莉是SS級的機率是P[i]j=0n1P[j]。請問,若你使用最佳的策略尋找SS級的蘿莉,所花費的鞭炮數的期望值X是多少?

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

Input Format

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

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

最後一個子任務為加分題。
對於該子任務,n800的限制不再適用。

Output Format

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

Sample Input 1

5
2 1 1 1 1

Sample Output 1

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