TopCoder

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

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

63.2% (24/38)

Tags

Description

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

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

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

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

Input Format

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

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

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

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

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

對於所有測資:

  • $1\leq N\leq 6\times 10^ 6$
  • $1\leq M\leq 10^ 9$
  • 一次執行中呼叫 calculate_distribution 的次數不超過 5 次。

對於 100 分的測資,$N\leq 3\times 10^ 5$。

Output Format

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

假設正確的期望值與標準差分別是 $\mu,\sigma$,而你回傳的期望值與標準差分別是 $\mu_1,\sigma_1$,若 $KL(N(\mu,\sigma) \parallel N(\mu_1,\sigma_1))\leq 10^ {-2}$,你的答案將會被視為正確。

註:$KL(P\parallel Q)$ 代表 KL divergence 、$N(\mu,\sigma)$ 代表常態分布。$KL(N(\mu,\sigma) \parallel N(\mu_1,\sigma_1))=\log\frac{\sigma_1}{\sigma}+\frac{\sigma^ 2-\sigma_1^ 2+(\mu-\mu_1)^ 2}{2\sigma_1^ 2}$。在 $\mu=\mu_1$ 的情況下,$KL(P\parallel Q)\leq 10^ {-2}$ 的條件大約是 $0.908\sigma\leq\sigma_1\leq 1.108\sigma$。

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

\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]

\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]

你只需要知道 $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) \parallel N(1.1,0.95))\approx 8.26\times 10^ {-3}\leq 10^ {-2}$,因此會被視為正確。

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

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

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