TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

63.2% (24/38)

Tags

Description

喵喵最近發明了一個神奇的遊戲。因為這個遊戲要丟非常多個硬幣,所以喵喵把它稱為「丟硬幣遊戲」。

這個遊戲的進行規則如下:首先,玩遊戲的人首先需要給出 N 個正整數 a1,a2,,aN,並且猜兩個數字 l,r,其中 0lrN。接著,假設這 N 個正整數中最大的數是 M,則喵喵會丟 M 個公正硬幣(出現正反面機率皆為 12,且每個硬幣的結果獨立),這些硬幣從 1 編號到 M,丟完後將丟出正面的所有硬幣編號寫下來。如果一開始的 N 個正整數中有被寫下來的數字個數 R 介於 lr 間,就算是贏了這一局。例如,如果一開始的 N 個正整數是 1,5,1,3,3,4,且最後丟出正面的硬幣編號是 1,2,4,因為給定的數字中有被寫下來的數字個數 R=3(兩個 1、一個 4),所以若 l3r 則遊玩者贏得這局。

喵喵很好奇對於不同的正整數序列,最後 R 的分布會有什麼不同。所以請你幫忙喵喵寫個程式,在給定 ai 的情況下幫喵喵計算最後 R 的期望值和標準差分別是多少。

由於喵喵的電腦記憶體不多,請避免在程式中引入 <iostream><bits/stdc++.h> 標頭檔,以免記憶體超出限制。

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

#include "lib2293.h"之後實作下列函數:
void calculate_distribution(int N, double* mean, double* stdev);

這個函數第一個參數 N 意義如題目所示。這個函數必須將所求的期望值存入第二個參數 mean 指向的 double,並將所求的標準差存入第三個參數 stdev 指向的 double。在一次執行中,這個函數將會被執行多次,所以請確保其有做好相關的初始化動作。

由於記憶體限制的緣故,這個函數中需要呼叫下列函數來分段取得 ai
int get_array(int C, int a[]);

每次呼叫這個函數,評測系統將會依序讀入 ai 中的接下來 C 個數字(也就是假設之前已經讀了 x 個數字,則會讀入 ax+1,ax+2,,ax+C),將結果存入 a 陣列後回傳 1。如果剩下的數字不足 C 個,評測系統將不會修改 a 陣列並直接回傳 0。呼叫此函數前請確認 a 至少能夠存下 C 個 int,否則將會產生不可預期的錯誤。

對於所有測資:

  • 1N6×106
  • 1M109
  • 一次執行中呼叫 calculate_distribution 的次數不超過 5 次。

對於 100 分的測資,N3×105

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

假設正確的期望值與標準差分別是 μ,σ,而你回傳的期望值與標準差分別是 μ1,σ1,若 KL(N(μ,σ)N(μ1,σ1))102,你的答案將會被視為正確。

註:KL(PQ) 代表 KL divergenceN(μ,σ) 代表常態分布KL(N(μ,σ)N(μ1,σ1))=logσ1σ+σ2σ12+(μμ1)22σ12。在 μ=μ1 的情況下,KL(PQ)102 的條件大約是 0.908σσ11.108σ

對於所有測資,若你的程式執行時間為時限的 x 倍(0x1),該筆測資的分數為 A×(p+qf(x)),其中 A 為該筆測資標示的分數、p,q 為各測資敘述上標示的常數,並給定常數 a=1,b=0.2

f(x)=(s(x)(bx)aba(bx)a1.1xa+(1s(x))(1x22))

s(x)={x,x{0,1}11+exp(8abcot(πxln20.1+lnb)),otherwise

你只需要知道 f(0)=1,f(1)=0,且 f(x) 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話,可以參考這個連結

Sample Input 1

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
1
2 1 1

Sample Output 1

注意:本題沒有輸出,本輸入為提供測試標頭檔(參見Hints)使用。
1.1 0.95

Hints

範例測資中,若 1 號硬幣是正面則 R=2,否則 R=0,因此 R 的期望值和標準差都是 1。由於 KL(N(1,1)N(1.1,0.95))8.26×103102,因此會被視為正確。

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:T(呼叫 calculate_distribution 的次數)
接下來 T 行:N,a1,a2,,aN

程式將會對每組測資輸出一行包含兩個浮點數,代表你回傳的值。

Problem Source

改編自 TIOJ 2076 / TIOJ 終極壓常數大賽 pB

Subtasks

No. Testdata Range Constraints Score
1 0 p=1,q=0.4 50
2 1 p=1,q=0.4 50
3 2 p=0,q=1 30
4 3 p=0,q=1 50
5 4 p=0,q=1 50
6 5 p=0,q=1 110
7 6 p=0,q=1 110

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 1192 4 1
1 2000 1192 4 2
2 2000 1192 4 3
3 2000 1192 4 4
4 2000 1192 4 5
5 2000 1192 4 6
6 2000 1192 4 7