Bài 2: Thi đấu (TS10 Hải Phòng thi thử - 2026)

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trung tâm thể thao thành phố tổ chức một giải đấu đối kháng giao lưu giữa hai đội tuyển trẻ. Để các trận đấu diễn ra cân bằng và hấp dẫn, ban tổ chức cần ghép các vận động viên của hai đội thành từng cặp thi đấu.

  • Đội \(A\)\(N\) vận động viên, vận động viên thứ \(i\) có trình độ \(a_i\).
  • Đội \(B\)\(M\) vận động viên, vận động viên thứ \(j\) có trình độ \(b_j\).

Một trận đấu chỉ được chấp nhận nếu hai vận động viên được ghép cặp có trình độ chênh lệch nhau không quá \(K\). Mỗi vận động viên chỉ được tham gia nhiều nhất một trận đấu.

Yêu cầu: Hãy lập trình xác định số lượng cặp thi đấu tối đa có thể được hình thành sao cho mọi cặp đều thỏa mãn điều kiện chênh lệch trình độ không quá \(K\).

Input

  • Dòng đầu tiên chứa ba số nguyên dương \(N, M, K\) (\(1 \le N, M \le 10^3, 0 \le K \le 100\)) lần lượt là số lượng các vận động viên trong đội \(A, B\) và độ chênh lệch.
  • Dòng thứ hai chứa dãy số \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^6\)), trong đó \(a_i\) là trình độ vận động viên thứ \(i\).
  • Dòng thứ ba chứa dãy số \(b_1, b_2, \dots, b_M\) (\(1 \le b_j \le 10^6\)) trong đó \(b_j\) là trình độ vận động viên thứ \(j\).

Output

  • Một số duy nhất là số lượng cặp đôi tối đa có thể được hình thành.

Example

Test 1

Input
4 5 1
1 4 6 2
5 1 5 7 9
Output
3
Note

Số cặp đôi có thể hình thành tối đa là \(3\) cặp đôi: \((1, 1); (4, 5); (6, 5)\).

Test 2

Input
4 4 3
4 2 3 4
8 9 8 10
Output
0
Note

Không có cặp đôi nào được hình thành thỏa mãn yêu cầu.

Bình luận (4)

Mới nhất
Tải bình luận...