VOI 11 Bài 4 - Nối điểm đen trắng

View as PDF

Submit solution


Points: 0.09 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI 2011
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.