USACO 2018 - Dec - Gold - Cowpatibility
Xem dạng PDF
Gửi bài giải
Điểm:
0,90 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Có một yếu tố quan trọng hơn cả để đánh giá 2 chú bò có phải bạn "tiềm năng" của nhau không, đó là vị kem yêu thích của chúng.
Nông dân John có ~N~ chú bò. Mỗi chú bò có đúng ~5~ vị kem yêu thích của riêng mình. Để thuận tiện, mỗi hương vị được thể hiện bởi một số nguyên dương tối đa là ~10^6~. Hai chú bò có thể kết bạn với nhau nếu có chung ít nhất một vị kem yêu thích.
Hãy đếm số cặp bò không kết bạn được với nhau.
Input
Dòng đầu là số nguyên dương ~N (1 \le N \le 50000)~ - số chú bò của nông dân John.
~N~ dòng tiếp theo, dòng thứ ~i~ gồm ~5~ số nguyên dương tối đa là ~10^6~ - các hương vị yêu thích của chù bò thứ ~i~.
Output
- Số cặp các chú bò không kết bạn được với nhau.
Sample Input
4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 90
Sample Output
4
Giải thích
- Các cặp bò không kết bạn được với nhau là ~ (1, 4) ~, ~ (2, 4) ~, ~ (3, 4) ~, ~ (1, 3) ~.
Bình luận
Spoiler thuật toán: