q373. 8. 超級變異數 - 高中生程式解題系統

Content

　　承上題。給定正整數 $N$，以及包含 $N$ 個正整數的序列 $a$。
定義「超級變異數」：

$$\text{sVar}_{[l, r]}=\frac{1}{r-l+1}\sum^{r}_{i=l}{(a_i-G_{[l, r]})^2}$$
　　其中 $G$ 為「幾何平均數」：

$$G_{[l, r]}=(\prod^{r}_{i=l}{a_i})^\frac{1}{r-l+1}$$

　　對於所有區間，請比較變異數 $\text{Var}_{[l, r]}$ 與超級變異數 $\text{sVar}_{[l, r]}$ 之大小關係。

Input

　　輸入的第一行有一個正整數 $N$（$1\le N\le 10^6$），代表序列 $a$ 的長度。
　　第二行有 $N$ 個正整數 $a_i$（$1\le a_i\le 10^9$），代表序列 $a$ 的元素內容。

Output

　　統計所有區間 $[l, r]$ 內，變異數 $\text{Var}_{[l, r]}$ 與超級變異數 $\text{sVar}_{[l, r]}$ 的比較結果，並輸出三個整數，分別表示：

第一個數字：符合 $\text{Var}_{[l, r]}<\text{sVars}_{[l, r]}$ 的區間數量
第二個數字：符合 $\text{Var}_{[l, r]}=\text{sVars}_{[l, r]}$ 的區間數量
第三個數字：符合 $\text{Var}_{[l, r]}>\text{sVars}_{[l, r]}$ 的區間數量

Sample Input #1

3
3 2 2

Sample Output #1

2 4 0

Sample Input #2

6
1 100 2 200 3 300

Sample Output #2

15 6 0

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <50M

Hint ：

　　「範例輸入 #1」的計算過程：

區間	$\text{Var}_{[l, r]}$		$\text{sVar}_{[l, r]}$
$[1, 1]$	$0$	$=$	$0$
$[1, 2]$	$0.25$	$<$	$0.5$
$[1, 3]$	$0.\overline 2$	$<$	$0.43\dots$
$[2, 2]$	$0$	$=$	$0$
$[2, 3]$	$0$	$=$	$0$
$[3, 3]$	$0$	$=$	$0$

共 $2$ 個 $<$、$4$ 個 $=$、$0$ 個 $>$。

本題共有 $2$ 個子題，每個子題有多筆測資。
第一子題：　$N\le 5$，全部解出可得 $10$ 分。
第二子題：　無其它限制，全部解出可得 $90$ 分。

Tags:

數學算幾不等式

出處:

113學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」