Codeforces 482A : Diverse Permutation
問題リンク : Problem - 482A - Codeforces
問題概要 :
n以下の異なる正の整数からなるパーミュテーションpについて考える
pの隣接する各要素の差分が異なるk個の数の集まりとなるようなpを出力せよ
解法 :
n = 7 について考える
k = 1 のとき、
1 2 3 4 5 6 7
k = 2 のとき、
1 2 3 4 5 7 6
k = 3 のとき、
1 2 3 4 7 5 6
k = 4 のとき、
1 2 3 7 4 6 5
k = 5 のとき、
1 2 7 3 6 4 5
k = 6 のとき、
1 7 2 6 3 5 4
わかりましたね?
ノートに色々書いていたら規則をみつけたのでそれ以上説明ができない。。
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int main(){ int n,k; cin >> n >> k; int maxi = n; int mini = n-k+1; bool phase = true; rep(i,n){ if( i ) printf(" "); if( i < n-k ) printf("%d",i+1); else { if( phase ) printf("%d",maxi--); else printf("%d",mini++); phase = !phase; } } puts(""); return 0; }