MCARDS - Card Sorting - Solution for SPOJ

Problem

https://vn.spoj.com/problems/MCARDS

https://oj.vnoi.info/problem/MCARDS

Mav có n*c quân bài; mỗi quân bài 1 màu; và mỗi màu có n quân bài. Mav muốn sắp xếp các quân bài cùng màu nằm cạnh nhau và chúng theo thứ tự tăng dần về giá trị.

Input

Dòng đầu là 2 số C (số màu), (1 ≤ C ≤ 4), và N, số quân bài cùng màu mỗi loại, (1 ≤ N ≤ 100).

N*C dòng tiếp theo mỗi dòng là 2 số nguyên X, Y; 1 ≤ X ≤ C, 1 ≤ Y ≤ N, là màu của quân bài và giá trị quân bài đó.

Thứ tự quân bài ban đầu (từ trái sang phải) chính là thứ tự dữ liệu input.

Output

Số lần chuyển bài ít nhất để thu được dãy bà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

Tutorial

Submission

MCARDS.cpp

Tutorial SPOJ

MCARDS - Card Sorting