MNERED - NERED

 

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:~!(*(@*!@^&
Ngày:2009-03-08
Thời gian chạy:0.185s
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
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
2012-08-03 02:58:13 KAKALOT
?
2009-06-01 16:38:07 ~!(*(@*!@^&
da chinh lai theo y kien cua Nuga
2009-05-05 04:27:54 Voyage
Em nghĩ để cho bài này thực sự hoàn chỉnh thì nên có thêm test cho trường hợp không chuyển được.
VD
2 3
1 1
1 1
1 3
2009-05-04 14:32:34 Race with time
Và trong phần đề tiếng Anh nhầm chỗ 1 <= M <= N2 (là N^2).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.