MAGPERM - Hoán vị thần kì
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho một mảng ~A~ gồm ~N~ phần tử và 1 số ~K~, các phần tử của mảng ~A~ được đánh số từ ~1~ đến ~N~. Gọi một hoán vị của mảng ~A~ là mảng ~B~. Hãy viết chương trình tìm xem liệu có hoán vị ~B~ nào thỏa mãn:
- Các phần tử ở cùng một vị trí trong cả ~A~ và ~B~ đều có chênh lệch bằng ~K~.
Ví dụ: Cho một mảng gồm ~4~ phần tử ~A = [1, 2, 3, 4]~ , ~K = 2~ . Thì ta tìm được một hoán vị ~B = [3, 4, 1, 2]~ thõa mãn điều kiện đề bài vì:
- Ta có ~B[0] - A[0] = 3 - 1 = 2~
- Ở các vị trí khác ta có ~A[2] - B[2] = 3 - 1 = 2~, tương tự với các vị trí còn lại.
Input
- Dòng 1 chứa số ~N~ là độ dài của mảng và 1 số ~K~
Biết rằng
- ~1 \le N \le 10^5~
- ~ 0 \le K < N~
Output
- Nếu có hoán vị ~B~ nào thỏa mãn đề bài, in ra hoán vị ~B~ đó, mỗi phần tử cách nhau 1 dấu cách.
- Nếu không có hoán vị ~B~ nào thỏa mãn đề bài, in ra ~-1~ .
Sample
Input #1
2 1
Output #1
2 1
Input #2
3 1
Output #2
-1
Input #3
3 0
Output #3
1 2 3
Bình luận
full AC nhé
include <bits/stdc++.h>
using namespace std;
int main() { int n; int k; cin >> n; cin >> k; vector<int> b(n+1,0); vector<bool> kt(n+1,false); for (int i=1;i<=n;++i) { int abs1=i+k; int abs2=i-k; if (abs2>=1 && kt[abs2]==false) { b[i]=abs2; kt[abs2]=true; } else if (abs1 <=n && kt[abs1]== false) { b[i]=abs1; kt[abs1]=true; } else { cout << "-1" << endl; return 0; } } for (int i=1;i<=n;++i) { cout << b[i] << " "; } return 0; }
người ta tự làm xong người ta giải thích chứ đâu bạn :))
mn ai giảng e vs
bạn đọc lời giải ở đâu v cho mình xin đc ko ạ