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

JOI 2006 問題4

1 から 2n の数が書かれた 2n 枚のカードがあり, 上から 1, 2, 3, ... , 2n の順に積み重なっている.

このカードを, 次の方法を何回か用いて並べ替える.

整数 k でカット
上から k 枚のカードの山 A と 残りのカードの山 B に分けた後, 山 A の上に山 B をのせる.
リフルシャッフル
上から n 枚の山 A と残りの山 B に分け, 上から A の1枚目, B の1枚目, A の2枚目, B の2枚目, …, A の n枚目, B の n枚目, となるようにして, 1 つの山にする.

入力ファイルの指示に従い, カードを並び替えたあとのカードの番号を, 上から順番に出力するプログラムを作成せよ.

  • 1 行目には n (1 ≦ n ≦ 100)が書かれている. すなわちカードの枚数は 2n 枚である.
  • 2 行目には操作の回数 m (1 ≦ m ≦ 1000)が書かれている.
  • 3 行目から m + 2 行目までの m 行には, 0 から 2n-1 までのいずれか 1 つの整数 k が書かれており, カードを並べ替える方法を順に指定している.
    • k = 0 の場合は, リフルシャッフルを行う.
    • 1 ≦ k ≦ 2n-1 の場合は, k でカットを行う.

2n 行からなる出力ファイルを提出せよ. 1 行目には並べ替え終了後の一番上のカードの番号, 2 行目には並べ替え終了後の上から 2 番目のカードの番号というように, i 行目には上から i 番目のカードの番号を出力せよ.

交換後の配列を作り、それを現在の並び方に格納するということをm回繰り返せば良いだろう。

#include <iostream>
#include <vector>
using namespace std;
int main() {
 int a[1000], n,m;//aは現在のカードの状況を格納
 cin >> n;
 for (int i = 1; i <= 2 * n; i++) {
  a[i] = i;//a[1]=1,a[2]=2...
 }
 cin >> m;
 for (int i = 0; i < m; i++) {
  vector<int>v(2 * n + 5);//交換後の状態を格納
  int k, j, now = 1;
  cin >> k;
  if (k == 0) {
   for (j = 1; j <= n; j++) {
    v[now] = a[j];
    now++;
    v[now] = a[j + n];
    now++;
   }
  }
  else {
   for (j = k + 1; j <= 2 * n; j++) {
    v[now] = a[j];
    now++;
   }
   for (j = 1; j <= k; j++) {
    v[now] = a[j];
    now++;
   }
  }
  for (j = 1; j <= 2 * n; j++) {
   a[j] = v[j];//交換後を現在に戻す
  }
 }
 for (int i = 1; i <= 2 * n; i++) {
  cout << a[i] << endl;
 }
 return 0;
}