APIO 2007 - Mobiles
Xem PDFBạn được nhờ mua một món quà cho em trai Ike. Tuy nhiên, Ike có sở thích rất riêng: em chỉ thích những món quà được sắp xếp theo đúng kiểu mình muốn.
Bạn tìm thấy một cửa hàng bán đồ chơi treo. Mỗi bộ đồ chơi treo là một vật trang trí nhiều tầng, thường được treo trên trần nhà, gồm các thanh ngang nối với nhau bằng dây thẳng đứng. Ở mỗi đầu của mỗi thanh có một sợi dây treo một thanh ngang khác hoặc một món đồ chơi.
Để Ike thích món quà, bạn cần tìm một bộ đồ chơi treo có thể được sắp xếp lại sao cho:
- Hai món đồ chơi bất kỳ nằm ở cùng một tầng (nghĩa là được nối với trần nhà qua cùng số thanh ngang), hoặc chỉ chênh nhau một tầng.
- Với hai món đồ chơi bất kỳ chênh nhau một tầng, món nằm bên trái phải ở thấp hơn món nằm bên phải.
Bạn có thể sắp xếp lại bằng các phép đổi chỗ. Trong một phép đổi chỗ, bạn chọn một thanh ngang, tháo những gì đang treo dưới hai đầu trái và phải của thanh, rồi treo chúng vào hai đầu đối diện. Phép đổi chỗ này không thay đổi thứ tự bên trong các phần được treo ở phía dưới.
Hãy xác định số phép đổi chỗ ít nhất để bộ đồ chơi treo thỏa mãn yêu cầu của Ike, hoặc cho biết không thể thực hiện được. Có thể giả sử các món đồ chơi không bao giờ vướng vào nhau.
Dữ liệu vào
Đọc từ đầu vào chuẩn.
Dòng đầu chứa số nguyên \(n\), là số thanh ngang. Các thanh được đánh số từ \(1\) đến \(n\).
Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l,r\), cách nhau bởi một dấu cách, mô tả vật được treo dưới đầu trái và đầu phải của thanh \(i\). Nếu vật đó là một món đồ chơi thì giá trị tương ứng bằng \(-1\); nếu là một thanh ngang thì giá trị tương ứng là số hiệu thanh đó.
Mọi thanh treo phía dưới thanh \(i\) đều có số hiệu lớn hơn \(i\). Thanh \(1\) là thanh duy nhất ở trên cùng.
Dữ liệu ra
Ghi ra đầu ra chuẩn một dòng chứa số nguyên là số phép đổi chỗ ít nhất cần thực hiện. Nếu không thể sắp xếp lại theo yêu cầu, in \(-1\).
Ràng buộc
- \(1 \le n \le 100\,000\).
- Dữ liệu mô tả một bộ đồ chơi treo hợp lệ theo các quy tắc trên.
Phân nhóm
Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm khi đúng toàn bộ test trong nhóm.
| Nhóm | Điểm | Điều kiện |
|---|---|---|
| Toàn bộ dữ liệu | 100 | \(1 \le n \le 100\,000\); không có ràng buộc bổ sung. |
Ví dụ
Ví dụ 1
Input
6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1Output
2Note
Bộ đồ chơi ban đầu có dạng sau:
Cấu hình này thỏa mãn điều kiện thứ nhất nhưng không thỏa mãn điều kiện thứ hai: món đồ chơi ngoài cùng bên trái ở cao hơn những món nằm bên phải nó.
Trước hết, đổi chỗ hai đầu của thanh \(1\). Thao tác này đổi vị trí của thanh \(2\) và thanh \(3\):
Sau đó, đổi chỗ hai đầu của thanh \(2\), đưa thanh \(4\) sang bên trái và món đồ chơi sang bên phải:
Cấu hình cuối cùng thỏa mãn yêu cầu: hai món đồ chơi bất kỳ chênh nhau nhiều nhất một tầng, và mọi món ở tầng thấp hơn đều nằm bên trái các món ở tầng cao hơn.
Nguồn
APIO 2007 — Mobiles.
Kỳ thi:
- APIO 2007 (12 Tháng năm, 2007)
Bình luận