TLEOJ Contest #16 - Trung bình hay trung vị

Điểm: 1800 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Dạng bài

Cho dãy số nguyên dương $a$ có $n$ phần tử, tìm số dãy con $b$ không rỗng của $a$ thỏa mãn đồng thời hai điều kiện sau:

Dãy $b$ có kích thước lẻ.
Trung bình cộng dãy $b$ nhỏ hơn trung vị dãy $b$

Dãy con

Một dãy con của một dãy số $a$ là một dãy số có thể thu được bằng cách xóa đi một số phần tử trong $a$ mà không thay đổi thứ tự các phần tử còn lại. Nói cách khác, nếu $a$ là dãy số $a_1, a_2, ..., a_n$ , thì một dãy con độ dài $k$ của $a$ sẽ có dạng $a_{i_1}, a_{i_2}, ..., a_{i_k}$ với $1 \leq i_1 < i_2 < ... < i_k \leq n$ .

Trung bình cộng là gì

Trung bình cộng của dãy $b$ có kích thước $m$ là $\frac{\sum^m_{i=1}b_i}{m}$ .

Trung vị là gì

Trung vị của dãy $b$ tăng dần có kích thước $m$ có giá trị bằng $b_{\frac{m+1}{2}}$ , nếu $b$ chưa được sắp xếp tăng dần, sắp xếp $b$ theo giá trị tăng dần rồi mới tìm trung vị.

Yêu cầu: In ra số dãy con thỏa mãn điều kiện theo $\text{mod}$ $998244353$ .

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên chứa số nguyên dương $n$ ( $1\le n\le 100$ ).
Dòng thứ hai gồm $n$ số nguyên dương $a_i$ ( $a_i\le 500$ ).

Output: (màn hình)

In ra số dãy con thỏa mãn điều kiện theo $\text{mod}$ $998244353$ .

Subtasks

Gọi $x=\text{max}(a_1,a_2,\dots,a_n)$

Subtask $1$ ( $20\%$ ) $n\le 10$ .
Subtask $2$ ( $20\%$ ) $n\le 50,x\le 100$ .
Subtask $3$ ( $20\%$ ) $x=2$ .
Subtask $4$ ( $40\%$ ) không có ràng buộc gì thêm.

Sample

Input (bàn phím)

5 
1 2 2 3 4

Output (màn hình)

Notes

Ta tìm được hai dãy con là:

$\{1;3;4\}$ có trung bình cộng là $\frac{1+3+4}{3}\approx 2.6$ , có trung vị là $3$ .
$\{1;2;2\}$ có trung bình cộng là $\frac{1+2+2}{3}\approx 1.6$ , có trung vị là $2$ .

Bình luận

Không có bình luận nào.