Mav có n*c quân bài; mỗi
quân bài 1 màu; và mỗi màu có n quân bài. Mav muốn sắp xếp các quân
bài cùng màu nằm cạnh nhau và chúng theo thứ tự tăng dần về giá
trị.
Input
Dòng đầu là 2 số C
(số màu), (1 ≤ C ≤ 4), và N, số quân bài cùng màu mỗi loại, (1 ≤ N ≤
100).
N*C dòng tiếp theo
mỗi dòng là 2 số nguyên X, Y; 1 ≤ X ≤ C, 1 ≤ Y ≤ N, là màu của quân bài
và giá trị quân bài đó.
Thứ tự quân bài ban
đầu (từ trái sang phải) chính là thứ tự dữ liệu input.
Output
Số lần chuyển bài
ít nhất để thu được dãy bài được sắp theo yêu cầu trên.
Sample
CARDS.IN
2 2
2 1
1 2
1 1
2 2
CARDS.OUT
2
CARDS.IN
4 1
2 1
3 1
1 1
4 1
CARDS.OUT
0
CARDS.IN
3 2
3 2
2 2
1 1
3 1
2 1
1 2
CARDS.OUT
2
=======================
Thuật toán đề xuất: cái này chom chỉa
trong KCBOOK....^^!
Đừng xem trọng việc mã hóa các màu từ 1
đến 4, ta coi D[i] là thứ tự của màu i trong dãy....
- Ta quay lui để xác định thứ tự
màu!
Ví dụ, ta có 4 màu, mà mảng X trong phần
quay lui là X = (1,3,2,4) thì:
+ D[1] := 1;
+ D[3] := 2;
+ D[2] := 3;
+ D[4] := 4;
-Sau khi có thứ tự màu, ta quy ước giá
trị "mới" của từng lá bài là: A[i] := D[mau[i]]*1000 +
gt[i]
với:
+ mau[i] : màu của quân bài i
+ gt[i]: giá trị cũ của
quân bài trong đề cho
