VOI 11 Bài 4 - Nối điểm đen trắng
Xem dạng PDF
Gửi bài giải
Điểm:
0,09 (OI)
Giới hạn thời gian:
0.6s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trên trục số thực cho ~n~ điểm đen và ~n~ điểm trắng hoàn toàn phân biệt. Các điểm đen có tọa độ nguyên ~a_1, a_2, ..., a_n~ còn các điểm trắng có tọa độ nguyên ~b_1, b_2, ..., b_n~. Người ta muốn chọn ra ~k~ điểm đen và ~k~ điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho ~k~ đoạn thẳng tạo được đôi một không có điểm chung.
Kết quả: Ghi ra một số nguyên duy nhất là số ~k~ lớn nhất tìm được
Input
- Dòng thứ nhất chứa số nguyên dương ~n\; (n \leq 10^5)~.
- Dòng thứ hai chứa các số ~a_1, a_2, ..., a_n\; (|a_i| \leq 10^9, i = 1, 2,..., n)~.
- Dòng thứ ba chứa các số ~b_1, b_2, ..., b_n\; (|b_i| \leq 10^9, i = 1, 2,..., n)~.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Cho tọa độ của ~n~ điểm đen ~a_1, a_2, ..., a_n~ và tọa độ của điểm trắng ~b_1, b_2, ..., b_n~. Hãy tìm giá trị ~k~ lớn nhất thỏa mãn yêu cầu trên.
Giới hạn
50% số test ứng với 50% số điểm của bài có ~1 \leq n \leq 100~
Sample Input
3
0 3 1
-3 5 -1
Sample Output
2
Note
Bình luận
Hint bài này: