Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MEDIAN - Phần tử trung vị

Cho một dãy số a1, a2, ..., an được sinh ngẫu nhiên như sau:

  • a1=seed
  • ai=(ai-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.

Được gửi lên bởi:Duc
Ngày:2008-09-14
Thời gian chạy:0.962s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:NUS ACM Training

hide comments
2019-01-11 16:04:08
bài này dùng trie nhị phân cũng hay nè :D

Last edit: 2019-01-11 16:04:44
2017-11-29 18:58:59
code PAS:https://ideone.com/bfm1lV
ledacthuongvq
2017-10-01 14:26:39
Có 2 cách
C1 : Bit - BS ( cách này cài nhanh nhưng chạy hơi chậm 1 chút )
C2: 2 Heap ( cách này cài khá lâu nhưng đpt lại tối ưu )
=> Ac

Last edit: 2017-10-01 15:56:56
2017-04-25 11:00:55
đề bóp dái ngưòi đọc
2017-04-22 05:33:09
bài này hay.
2016-10-22 11:49:44
Bài này dùng thư viện C++ thì chả nói làm gì :v
2016-10-10 19:50:35 THK6
190 dòng + 3 day = 1 đấm AC :'(
2016-05-27 18:27:37
Dùng Heap giống bài MSE07B AC :)))
2016-05-18 15:55:17 Nguyen Cuong
nghi ngờ test yếu quá :/ code mình đpt O(t * n * log2(65536) * log2(65536)) mà vẫn AC :/

Last edit: 2016-05-18 16:10:35
2015-10-30 05:15:02 phạm minh khiêm
trâu cũng qua :)))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.