Hoán vị thần kì - LCOJ: Luyen Code Online

MAGPERM - Hoán vị thần kì

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Tác giả:

wronganswer

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

Hãy đọc nội quy trước khi bình luận.

4
chuduchieu88d88s100zz1000z đã bình luận lúc 3, Tháng 4, 2024, 17:44
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)

{

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++;

}

}

}

}

-1

dinhvantung0611 đã bình luận lúc 11, Tháng 3, 2024, 9:41

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))

0

longzuhaun đã bình luận lúc 29, Tháng 2, 2024, 10:21

mn ai giảng e vs

-1

import java.util.Scanner;

public class MAGPERM { public static void main(String[] args) { Scanner sc = new Scanner(System.in);

    int n = sc.nextInt(), k = sc.nextInt();
    if (k == 0) {
        for (int i = 1; i <= n; i++) {
            System.out.print(i + " ");
        }
    } else if ((n/k) % 2 == 0) {
        int d = 1, d1 = 0;
        for (int i = 1; i <= n; i++) {
            if (d1 < k) d1++;
            else {
                d1 = 1;
                d++;
            }
            //System.out.println(i + "\t" + d1 + "\t" + d);
            if (d % 2 != 0) System.out.printf("%d ", i + k);
            else System.out.printf("%d ", i - k);
        }
    } else System.out.println("-1");

    sc.close();
}

}

-1

include <stdio.h>

int main(){
int n,k;
scanf("%d%d",&n,&k);
int a[n];
for(int i=1;i<=n;i++){
    a[i] = i;
}
if(k==0){
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}
if(k == (float) n/2 ){
    for(int i=1;i<=n;i++){
        if(a[i]<=k) printf("%d ",a[i]+k);
        else printf("%d ",a[i]-k);
    }
}
else printf("-1");

} mn ơi em chưa vét hết th ạ

0

Nguyenkhanhtung đã bình luận lúc 15, Tháng 12, 2023, 6:16

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; }

int a[n];
for(int i = 0;i&lt;n;i++)
{
    a[i] = i + 1;
}
int b[n];
if(k!=0&&(n/k)%2==0)
{
    int dau = 1;
    for(int i = 0;i&lt;n;i +=k)
    {
        for(int j = i;j&lt;i+k;j++)
        {
            b[j] = a[j] + dau*k;
        }
        dau *= -1;
    }
    for(int i = 0;i&lt;n;i++)
    {
        cout<&lt;b[i]<<" ";
    }
}
else if(k==0)
    {
        for(int i = 0;i&lt;n;i++)
        {
            cout<&lt;a[i]<<" ";
        }
    }
else 
    cout<<"-1";

return 0;

}

-7

Yorickur đã bình luận lúc 13, Tháng 8, 2023, 15:01

dạ có ai có thể giúp mình câu này được không ạ, mình đọc các lời giải mà thực sự không hiểu tại sao mình thấy mọi người có điều kiện nếu n % 2 * k != 0 thì sẽ không có hoán vị là tại sao ạ, mong mn giải thích cho mình vs. Xin cảm ơn mn.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

8

tognoek đã bình luận lúc 27, Tháng 8, 2023, 2:54

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

3

lebahieu đã bình luận lúc 19, Tháng 8, 2023, 9:59

bạn đọc lời giải ở đâu v cho mình xin đc ko ạ