Submit solution
Points:
0.36 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho hình vuông ~N \times N~, một số ô có các hộp, mỗi ô có thể có nhiều hộp bao nhau. Tính số hộp cần chuyển ít nhất để các hộp này xếp thành ~1~ hình chữ nhật (mỗi ô chỉ có ~1~ hộp). Phép chuyển hộp là chuyển ~1~ hộp ở trên cùng ở một ô vuông sang và đặt ở trên cùng ~1~ ô vuông nào khác.
Input
DÒng đầu là ~2~ số ~N~ và ~M~, ~(1 \leq N \leq 100~, ~1 \leq M \leq N^{2})~, kích thước hình vuông và số hộp. ~M~ dòng tiếp theo là tọa độ mỗi hộp (hàng, cột).
Output
Số hộp ít nhất cần chuyển
Sample Input 1
4 3
2 2
4 4
1 1
Sample Output 1
2
Sample Input 2
5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3
Sample Output 2
3
Note
Ở ví dụ ~2~, hộp chuyển từ ~(2~, ~3)~ tới ~(3~, ~3)~, từ ~(4~, ~2)~ tới ~(2~, ~5)~ và từ ~(4~, ~4)~ tới ~(3~, ~5)~.
Comments