Giữ chuẩn trung bình Top-k

Bối cảnh

Một bảng xếp hạng có n score. Với ngưỡng T, ban tổ chức muốn lấy nhiều người nhất từ đầu bảng sao cho trung bình score của nhóm top-k vẫn không nhỏ hơn T. Nếu ngay người đứng đầu cũng thấp hơn T thì đáp án là 0.

Sau sort giảm dần, trung bình của top-k không tăng khi k tăng: thêm một người có score không lớn hơn những người trước không thể làm average tăng. Vì vậy predicate average(top-k) ≥ T là true ở một prefix rồi chuyển sang false. Không cần dùng số thực; điều kiện tương đương pre[k] ≥ T*k, tránh sai số. Bài Medium kết hợp comparator mặc định, prefix và binary search trên một điều kiện trung bình.

Điểm đáng suy nghĩ là predicate không nằm trực tiếp trên từng phần tử mà trên trung bình của prefix. Nếu dùng số thực, sai số ở các test biên có thể làm boundary lệch một đơn vị. Việc nhân chéo pre[k] ≥ T*k vừa chính xác vừa làm điều kiện monotonic hiện ra rõ hơn. Đây là thói quen rất hữu ích trong các bài thi có tỷ lệ, trung bình và phân số.

Yêu cầu

1. Sort score giảm dần.
2. Build prefix.
3. Với mỗi T, tìm k lớn nhất sao cho pre[k] ≥ T*k.
4. Cho phép k=0.
5. In k.

Input

Dòng 1 n; dòng 2 n score; dòng 3 q; q dòng T.

Output

q dòng k.

Ràng buộc

1≤n,q≤5000, 0≤score,T≤10^9.

Ví dụ 1

Input

5
100 90 80 70 60
5
95
90
80
60
101

Output

2
3
5
5
0

Giải thích

Ranking 100 90 80 70 60 có prefix 0,100,190,270,340,400. Với T=95, k=1 thỏa 100≥95 nhưng k=2 cần 190≥190 cũng thỏa, k=3 cần 270≥285 sai, nên max k=2. T=90 cũng cho k=3 vì 270=90×3. T=80 cho k=5 vì average toàn đội=80. T=60 cũng lấy 5; T=101 lấy 0.

Ví dụ 2

Input

4
10 10 10 10
3
10
9
11

Output

4
4
0

Giải thích

Tất cả score đều 10. Với T=10, mọi k từ 1 đến 4 đều có average đúng 10 nên lấy tối đa 4. T=9 cũng lấy 4. T=11 thì ngay top1=10<11 nên không có k dương hợp lệ, output 0.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: sort descending, prefix sum, average condition, binary search, integer comparison
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100