VOROOM - Xếp phòng
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274861/problem/M
https://codeforces.com/group/FLVn1Sc504/contest/271722/problem/C
Bé Linh tham gia Hội thi "Bé trẻ bé trâu" do trường mầm non Chuyên Bắp Rang tổ chức. Tại đây, bé được ban tổ chức sắp xếp cho ở khách sạn miễn phí. Ngoài bé Linh, cuộc thi này còn có sự tham gia của N sửu nhi khác đến từ nhiều quốc gia khác. Khách sạn có N+1 phòng cho N+1 sửu nhi ở riêng. Để chiều lòng các sửu nhi, trước ngày thi, các sửu nhi sẽ được xem ảnh của tất cả các phòng, sau đó chọn ra hai trong số N+1 phòng mà mình thích, và ban tổ chức sẽ cho các sửu nhi ở một trong hai phòng này. Tuy nhiên, do mải mê đào mộ FB của chính mình, bé Linh quên mất việc cung cấp cho ban tổ chức 2 phòng mình thích. Đến ngày thi, bé Linh đã làm quen và biết được các cặp phòng mà các sửu nhi khác đã chọn. Là người dễ tính, bé Linh có thể ở bất kỳ phòng nào, vì vậy bé Linh cần biết số cách chọn 2 phòng khác nhau sao cho ban tổ chức có thể sắp xếp được phòng cho tất cả mọi người. Bé Linh có 1 chiếc laptop và nhờ bạn viết một chương trình tính con số này. Tuy nhiên, do laptop bị dán quá nhiều tranh ảnh doraemon nên thường xuyên bị nóng máy cháy bugi. Vì vậy, nếu chương trình của bạn chạy quá 1s máy có thể phát nổ.
Bé Linh tham gia Hội thi "Bé trẻ bé trâu" do trường mầm non Chuyên Bắp Rang tổ chức. Tại đây, bé được ban tổ chức sắp xếp cho ở khách sạn miễn phí.
Ngoài bé Linh, cuộc thi này còn có sự tham gia của N sửu nhi đến từ nhiều nơi khác. Khách sạn có N + 1 phòng cho N + 1 sửu nhi ở riêng. Để chiều lòng các sửu nhi, trước ngày thi, các sửu nhi sẽ được xem ảnh của tất cả các phòng, sau đó chọn ra hai trong số N + 1 phòng mà mình thích, và ban tổ chức sẽ tìm cách sắp xếp cho các sửu nhi ở một trong hai phòng này.
Tuy nhiên, do mải mê đào mộ FB và like post của chính mình, bé Linh quên mất việc cung cấp cho ban tổ chức hai phòng mình thích. Đến ngày thi, bé Linh đã làm quen và biết được các cặp phòng mà các sửu nhi khác đã chọn. Là người dễ tính, bé Linh có thể ở bất kỳ phòng nào, vì vậy bé chỉ cần biết số cách chọn 2 phòng khác nhau sao cho ban tổ chức có thể sắp xếp được phòng cho tất cả mọi người.
Bé Linh có một chiếc laptop và nhờ bạn viết chương trình tính toán con số này. Tuy nhiên do laptop bị dán quá nhiều tranh ảnh doraemon nên hay bị nóng máy cháy bugi. Vì vậy chương trình của bạn cần chạy trong thời gian không quá 1s, bởi nếu quá thời gian này, máy có thể phát nổ và gây nguy hiểm tới tính mạng của chủ sở hữu.
Input
Dòng đầu chứa số nguyên N .
N dòng tiếp theo, dòng thứ i chứa cặp số nguyên A i , B i là 2 phòng mà bé thứ i đã lựa chọn. 1 ≤ A i < B i ≤ N + 1.
Output
Chứa một số duy nhất là đáp số bài toán.
Giới hạn
Subtask 1 (25%): N ≤ 15
Subtask 2 (35%): 16 ≤ N ≤ 50
Subtask 3 (40%): 51 ≤ N ≤ 2 * 10 5
Ví dụ
Input 1: 2 2 3 2 3
Output 1: 2
Input 2: 3 1 2 1 2 1 2
Output 2: 0
Giải thích:
Ví dụ 1 : Do 2 người 1 và 2 đều thích 2 phòng 2 và 3 nên 2 phòng này sẽ chia cho 2 người. Bé Linh chỉ có thể ở phòng 1. Vì vậy 2 cách chọn cặp phòng phù hợp cho bé là (1,2) và (1,3) .
Ví dụ 2 : Do có 3 người chỉ thích 2 phòng 1 và 2 nên dù bé Linh chọn phòng như thế nào, khách sạn cũng không thể xếp phòng được.
- Người up: voj
- Nguồn bài: VNOI Online 2016