Buổi hòa nhạc
Xem dạng PDF
Gửi bài giải
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig
Điểm:
800 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
Buổi hòa nhạc của có ~N \times M~ chỗ ngồi và ~\frac{N \times M} {2}~ cặp đôi đến tham dự. Chỗ ngồi của họ đã được đặt trước.
Tuy nhiên một vài người họ đã không hài lòng và đã đề nghị đổi vị trí với nhau sao cho cặp đôi nào cũng được ngồi gần nhau. Một cặp đôi được gọi là ngồi gần nhau khi họ ngồi cạnh nhau cùng hàng hoặc ngồi cạnh nhau cùng cột.
Để đảm bảo trật tự cho buổi hòa nhạc bạn hãy giúp họ chọn ra số người ít nhất được đổi chỗ để cặp đôi nào cũng được ngồi gần nhau.
~\texttt{Input}~
- Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ là kích thước của khán đài.
- ~N~ dòng tiếp theo mỗi dòng chứa ~M~ số nguyên ~x~ (~1 \le x \le \frac{N \times M} {2}~), các cặp đôi được biểu thị bởi các số nguyên giống nhau.
~\texttt{Output}~
- Gồm một dòng duy nhất là số người tối thiểu cần được đổi chỗ.
~\texttt{Constraint}~
- ~N~, ~M \leq 80~.
- Dữ liệu đảm bảo không có ai phải đi một mình.
~\texttt{Subtask}~
- Subtask ~1 \space (30\%)~: ~N~, ~M \le 8~.
- Subtask ~2 \space (70\%)~: Không có giới hạn gì thêm.
~\texttt{Sample Input}~
4 3
1 2 2
3 1 4
5 5 6
3 6 4
~\texttt{Sample Output}~
4
~\texttt{Note}~
- Các vị trí cần đổi chỗ là ~(2, 1)~, ~(2, 2)~, ~(4, 2)~, ~(4, 3)~.
Bình luận
Xin sol bài này với mọi người :((