[Đại học Vinh - TS10 - 2025] Bài 3: Quà cứu trợ

Xem dạng PDF

Gửi bài giải

Điểm: 9,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong một vùng bị thiên tai, có ~n~ gia đình khó khăn cần được hỗ trợ. Mỗi gia đình có một mức nhu cầu hỗ trợ riêng được biểu diễn bằng một số nguyên dương ~a_i~ (~i = 1, 2, ..., n~). Một tổ chức cứu trợ chuẩn bị ~m~ gói quà với giá trị của mỗi gói quà được biểu diễn bằng một số nguyên dương ~b_j~ (~j = 1, 2, ..., m~) để hỗ trợ các gia đình khó khăn. Tổ chức cứu trợ sẽ phát các gói quà theo nguyên tắc: nếu mỗi gia đình có nhu cầu mong muốn là ~a_i~ thì gia đình đó sẽ nhận được chỉ một gói quà có giá trị thuộc đoạn ~[a_i - k; a_i + k]~ với ~k~ là một số nguyên không âm.

Yêu cầu: Viết chương trình giúp tổ chức cứu trợ phân chia các gói quà để phát được cho nhiều gia đình nhất.

INPUT

Dòng 1 gồm ~3~ số nguyên dương ~n, m, k~ (~1 \le n \le 2 \times 10^5;~ ~1 \le m \le n;~ ~0 \le k \le 10^5~), mỗi số cách nhau ít nhất một dấu cách.

Dòng 2 gồm ~n~ số nguyên dương ~a_i~ (~10^5 \le a_i \le 10^8; 1 \le i \le n~), mỗi số cách nhau ít nhất một dấu cách.

Dòng 3 gồm ~m~ số nguyên dương ~b_j~ (~10^5 \le b_j \le 10^8;~ ~1 \le j \le m~), mỗi số cách nhau ít nhất một dấu cách.

OUTPUT

Gồm một dòng chứa số lượng gia đình nhiều nhất nhận được các gói quà.

SAMPLE INPUT 1

4 3 5
60 45 80 90
30 60 75

SAMPLE OUTPUT 1

2

Giải thích: Vì ~k = 5~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:

  • ~01~ gia đình có nhu cầu cần hỗ trợ ~60~, giá trị gói quà ~60~
  • ~01~ gia đình có nhu cầu cần hỗ trợ ~80~, giá trị gói quà ~75~

SAMPLE INPUT 2

5 2 3
21 15 35 10 40
32 16

SAMPLE OUTPUT 2

2

Giải thích: Vì ~k = 3~ nên có 2 gia đình nhận được gói quà phù hợp với nguyên tắc chia quà, cụ thể:

  • ~01~ gia đình có nhu cầu cần hỗ trợ ~35~, giá trị gói quà ~32~
  • ~01~ gia đình có nhu cầu cần hỗ trợ ~15~, giá trị gói quà ~16~

SUBTASKS

Subtask Điểm Ràng buộc
1 ~50\%~ ~1 \le n \le 10^4;~ ~1 \le m \le n~
2 ~30\%~ ~10^4 < n \le 10^5;~ ~10^4 < m \le n~
3 ~20\%~ ~10^5 < n \le 2 \times 10^5;~ ~10^5 < m \le n~

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.