| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P166SUMA - ROUND 6A - Captain Boomerang |
Captain Boomerang là người có khả năng rất đặc biệt. Như biệt danh của mình, anh là master trong việc sử dụng những chiếc boomerang. Ngoài ra, Captain Boomerang còn có sở thích rất kỳ lạ đó là thích chơi với các dãy hoán vị. Trong lúc rảnh rỗi, anh có nghĩ ra bài toán này và đem đi đố mọi người trong team.
Cho 1 dãy gồm n phần tử: a1, a2, …, an (1 <= ai <= 5000). Nhiệm vụ là phải chuyển dãy trên về 1 dãy hoán vị n phần tử, biết trong 1 bước, chỉ được thay đổi giá trị của 1 phần tử. Hỏi xem cần tối thiếu bao nhiêu bước để hoàn thành nhiệm vụ.
Biết rằng 1 dãy hoán vị n phần tử là hoán vị bất kỳ của dãy số 1, 2, 3, …, n
Do không ai trong team có sở thích kỳ lạ này nên cũng chẳng ai muốn làm, các bạn hãy giải đáp bài toán này của Captain Boomerang nhé.
Input
Dòng đầu tiên nhập 1 nguyên số n (1 <= n <= 5000).
Dòng tiếp theo nhập dãy gồm n số a1, a2, …, an (1 <= ai <= 5000).
Output
In ra kết quả bài toán – số bước ít nhất cần thực hiện.
Example
Test 1:
Input:
5
4 5 4 4 1
Output:
2
Test 2:
Input:
2
1 1
Output:
1
Giải thích test 1: 4 5 4 4 1 => 4 5 2 3 1 => cần 2 bước
| Được gửi lên bởi: | adm |
| Ngày: | 2016-08-12 |
| 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: | 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 |
hide comments
|
2018-02-26 17:45:18
P166SUMA: https://e16cn-ptit.blogspot.com/2018/02/p166suma-round-6a-captain-boomerang.html |
|
|
2017-07-28 11:51:00
cụ thể hơn là a[i]<=n |
