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, 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
code full ac nhá
include<bits/stdc++.h>
using namespace std;
int main()
{
long int n, k;
long int i, j, cnt=0;
cin >> n >> k;
if(k > n/2) cout << "-1";
else if(k==0)
{
for(i=1; i<=n; i++) cout << i << " ";
}
else if(k==1)
{
if(n==2) cout << 2 << " " << 1;
else if(n>=3) cout << "-1";
}
else
{
int q=0;
for(i=1; i<=k; i++)
{
for(j=n+1-k; j<=n; j++)
{
if((j-i)%k==0 && ((j-i)/k)%2 == 0)
{
}
if(q==1)
{
}
if(q==0)
{
for(i=1; i<=n; i++)
{
if(cnt/k % 2 == 0) cout << i+k << " ";
else if(cnt/k % 2 == 1) cout << i-k << " ";
cnt++;
}
}
}
}
Mình chia sẻ 3 test để các bạn có thể rút ra quy luật.
INPUT:
16 8
OUTPUT:
9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 (Cái test này tương tự như với INPUT: 4 2. Chắc nhiều bạn đã nhận ra là k = n / 2)
INPUT:
16 4
OUTPUT:
5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12 (Dễ thấy ta có 16 / 4 = 4 cặp. (5, 6, 7, 8), (1, 2, 3, 4), (13, 14, 15, 16), (9, 10, 11, 12))
INPUT:
16 2
OUTPUT:
3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 (Dễ thấy ta có 16 / 2 = 8 cặp. (3, 4), (1, 2), (7, 8), (5, 6), (11, 12), (9, 10), (15, 16), (13, 14))
mn ai giảng e vs
import java.util.Scanner;
public class MAGPERM { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
}
include <stdio.h>
} mn ơi em chưa vét hết th ạ
code cho ae nào cần.
include<bits/stdc++.h>
using namespace std; int main() { long int n, k; long int i, j, cnt=0; cin >> n >> k; if(k > n/2) cout << "-1"; else if(k==0) { for(i=1; i<=n; i++) cout << i << " "; } else if(k==1) { if(n==2) cout << 2 << " " << 1; else if(n>=3) cout << "-1"; } else { int q=0; for(i=1; i<=k; i++) { for(j=n+1-k; j<=n; j++) { if((j-i)%k==0 && ((j-i)/k)%2 == 0) { q=1; break; } } if(q==1) { cout << "-1"; break; } } if(q==0) { for(i=1; i<=n; i++) { if(cnt/k % 2 == 0) cout << i+k << " "; else if(cnt/k % 2 == 1) cout << i-k << " "; cnt++; } } } }
include <iostream>
using namespace std;
include <math.h>
int main() { int n, k; cin>>n>>k; if(k<0||k>=n||n>pow(10,5)) { cout<<"-1"; return 0; }
}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
giải thích theo ý mình hiểu sẽ như này: trước hết thì mảng a phải chia được thành 2 phần, phần trước +k, phần sau -k, với điều này thì sẽ thỏa mã, nhưng nếu mảng chia thành 4 phần thì sao, 1 sẽ là -k 2 là +k 3 là -k và 4 là -k, vậy thì số phần có thể chia chỉ có thể là 2 * k tại vì 2 * k phải bé hơn hoặc bằng N, vì nếu lớn hơn thì ở phần từ sẽ tạo ra số âm, và phần cộng sẽ tạo ra số lớn hơn N, ví dụ ha: N = 4 và k = 3, thì [1, 2] sẽ cộng và [3, 4] sẽ trừ => [4, 5] và [0, 1], mong các bạn hiểu và đóng góp
bạn đọc lời giải ở đâu v cho mình xin đc ko ạ