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

View as PDF

Submit solution

Points: 1800 (partial)
Time limit: 1.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type

Cho dãy số nguyên dương an 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\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)
2
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.

Comments

There are no comments at the moment.