1714 . 尋找蘿莉第二彈 - EX

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

eric_xiao

User's AC Ratio

50.0% (5/10)

Submission's AC Ratio

28.0% (21/75)

Tags

CKsim 2016-CKsim-5th

Description

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

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

Input Format

第一行有一個正整數 n≤2×105 代表蘿莉的數量，
接著第二行會有 n 個正整數，分別代表 P[0],⋯,P[n−1]，其中 P[i]≤109。

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

Output Format

為了方便，請輸出 X×∑i=0n−1P[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

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 (VSS, 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
Submit
Back to Top