| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P142PROB - ROUND 2B - Swap |
Cho trước một hoán vị gồm n phần tử và m phép đổi chỗ 2 phần tử. Nhiệm vụ của bạn là thực hiện các phép đổi chỗ một cách hợp lý, sao cho thu được hoán vị thỏa mãn là dãy số tăng dần (tức là dãy hoán vị 1, 2, 3, ... n).
Input
Dòng đầu tiên là 2 số nguyên n (1 <= n <= 12) và m (1 <= m <= n*(n-1)/2) tương ứng là số phần tử và số phép đổi chỗ.
Dòng thứ 2 gồm n số là một hoán vị của dãy 1,2,..., n.
M dòng tiếp theo, dòng thứ i gồm 2 số A_i và B_i, có nghĩa là phép biến đổi thực hiện đổi chỗ số thứ A_i và B_i. Các phép đổi chỗ là riêng biệt.
Input luôn được đảm bảo có đáp án.
Output
In ra một số nguyên duy nhất là số lần thực hiện các phép biến đổi ít nhất.
Example
Test 1:
Input:
2 1
2 1
1 2
Output:
1
Test 2:
Input:
3 2
2 1 3
1 3
2 3
Output:
3
Giải thích test 2:
Thứ tự thực hiện các phép đổi chỗ là 2 1 2.
Test 3:
Input:
5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5
Output:
0
| Được gửi lên bởi: | adm |
| Ngày: | 2014-02-08 |
| Thời gian chạy: | 1.5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
