MEDIAN - Phần tử trung vị
Giới hạn- Thời gian: 0.962s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một dãy số a1, a2, ..., an được sinh ngẫu nhiên như sau:
- a1=seed
- a i =(a i-1 *mul+add)%65536
Với mul, add, seed là các số cho trước.
Cho một số k ≤ n. Dãy đã cho có n-k+1 dãy con độ dài k. Hãy tính tổng tất cả các phần tử trung vị (phần tử nhỏ thứ (k+1)/2) của n-k+1 dãy con này).
Dữ liệu
Dòng đầu tiên chứa số test (không quá 30). Mỗi dòng tiếp theo chứa 5 số nguyên seed, mul, add, N, K. (0 ≤ seed, mul, add ≤ 65535, 1 ≤ N ≤ 250000, 1 ≤ K ≤ 5000, K ≤ N)
Kết quả
Với mỗi test in ra số hiệu test (theo mẫu) cùng với tổng các trung vị tìm được.
Ví dụ
Dữ liệu 5 3 1 1 10 3 10 0 13 5 2 4123 2341 1231 7 3 47 5621 1 125000 1700 32321 46543 32552 17 17 Kết quả Case #1: 60 Case #2: 49 Case #3: 102186 Case #4: 4040137193 Case #5: 25569 Giải thích Với test 1, dãy sinh ra là 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. Các dãy con là (3, 4, 5), ..., (10, 11, 12). Các trung vị là 4, 5, ..., 11.
- Người up: paulmcvn
- Nguồn bài: NUS ACM Training