Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
POSLOZI - POSLOZI |
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/poslozi
"Sắp xếp" là một trò chơi Flash đang thịnh hành hiện nay. Trong trò chơi này, người chơi được cho một hoán vị của các số từ 1 đén N và một dãy các phép tráo đổi. Sau đó, anh ta phải sử dụng các phép tráo đổi này để biến hoán vị ban đầu thành dãy 1, 2, 3, ..., N.
Để phá được kỉ lục, bạn cần phải sử dụng ít phép tráo đổi nhất. Bạn không thể làm được, nhưng bạn có thể lập trình ra một chương trình giúp bạn thực hiện điều đó!
Input
- Dòng thứ 1: Ghi 2 số nguyên N (1 ≤ N ≤ 12), độ dài của dãy số, và M (1 ≤ M ≤ N*(N-1)/2), số các phép biến đổi.
- Dòng thứ 2: Ghi một hoán vị các số nguyên từ 1 đến N.
- M dòng tiếp theo: Mỗi dòng mô tả một phép tráo đổi. Nếu dòng đó ghi hai số nguyên A và B thì bạn có thể hoán đổi vị trí của 2 số ở vị trí thứ A và vị trí thứ B cho nhau trong dãy số. Sẽ không có 2 phép biến đổi nào giống nhau.
Chú ý: Input luôn đảm bảo tồn tại một dãy các phép tráo đổi thỏa mãn đề bài.
Output
- Gồm 1 dòng duy nhất: Ghi ra số phép biến đổi ít nhất cần sử dụng.
Example
Input:
3 2
2 1 3
1 3
2 3
Output:
3
Được gửi lên bởi: | khanhptnk |
Ngày: | 2009-11-29 |
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ừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET |
Nguồn bài: | COCI contest 2, problem 5 |