読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

Codeforces 482A : Diverse Permutation

Codeforces

問題リンク : 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;
}