Cho hai đường thẳng song
song nằm ngang a và b. Trên mỗi đường thẳng, người ta chọn
lấy n
điểm phân biệt và gán cho mỗi điểm một số nguyên dương là nhãn của điểm đó:
+ Trên đường thẳng a,
điểm thứ i (theo thứ tự từ trái qua phải) được gán nhãn là ai.
+ Trên đường thẳng b,
điểm thứ j (Theo thứ tự từ trái qua phải) được gán nhãn là bj.
Ở đây (a1,
a2,…,an) và (b1, b2,…,bn)
là những hoán vị của dãy số (1, 2,…,n)
Yêu cầu:
Hãy chỉ ra một số tối đa các đoạn thẳng thỏa mãn:
+ Mỗi đoạn
thẳng phải nối hai điểm có cùng một nhãn: Một điểm trên đường thẳng a
và một điểm trên đường thẳng b.
+ Các đoạn
thẳng đôi một không có điểm chung
Dữ
liệu: Vào từ tệp văn bản LINES.INP
+ Dòng 1: chứa số nguyên dương n ≤ 105
+ Dòng 2: chứa n số theo thứ tự là a1, a2,…,an
+ Dòng 3: Chứa n số theo thứ tự là b1, b2,…,bn
Kết quả: Ghi ra tệp văn bản
LINES.OUT
+ Dòng 1: ghi số k là số đoạn thẳng nối được.
+ Dòng 2: Ghi k nhãn của các đoạn thẳng
được chọn (nhãn của mỗi đoạn thẳng là nhãn của điểm đầu mút)
Các số trên một dòng trong tệp
input/output được/phải ghi cách nhau ít nhất một ký tự trắng.
Ví dụ:
LINES.INP
|
LINES.OUT
|
6
2 3 1
5 6 4
3 2 5
6 1 4
|
4
3 4 5
6
|
