MNERED - NERED

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mnered


Cho hình vuông NxN, 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 ≤ N ≤ 100, 1 ≤ M ≤ 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
4 3
2 2
4 4
1 1
output
2

input
5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3
output
3

Ở 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).


Được gửi lên bởi:psetter
Ngày:2009-03-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 6th 09

hide comments
2021-05-27 18:02:00
Tham khảo: https://vnspoj.github.io/problems/MNERED
2017-10-05 03:36:34
Trau cung ac
2017-09-20 16:08:04
Đề này có thể có những trường hợp không chuyển được không? Chẳng hạn có 3 hộp mà N lại bằng 2.
Lúc này hình chữ nhật chỉ có thể xếp là 1x3 hay 3x1 không thể xếp được.
2017-09-12 13:18:25
Trâu = AC :3
2014-09-23 14:24:38 Thần Ðồng Mẫu Giáo
bài gì mà không có giới hạn :3
2014-08-18 13:58:13 Bùi Hữu Giáp
Toàn sai Test thứ 10 mới chết chứ!
2013-11-12 17:01:43 In God We Trust
sai test cuối vãi
2013-06-14 14:21:10 Bitagi97
bài này làm khó chịu quá đi

Last edit: 2013-07-10 04:10:51
2013-06-12 15:45:03 a;slkfjasl;fkj
làm thế nào ta?
2013-05-27 18:03:20 ‡■■Lãng du■■‡
::::==== Anh Voyage
Sao hinh vuông 2x2 lại có ô 1 3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.