PKU 3705 - Reverse

PKU

問題概要

nが入力される。
1, 2, ..., nの昇順数列をn, n-1, ..., 1の降順数列にするための最小の操作数と、操作方法を出力せよ。
数列に対する１回の操作では、次のことをできる。

  • (pos1, length, pos2)
    • まず、数列のpos1番目からlength個を取り出す。
    • 次に、取り出した後の数列のpos2番目の要素の直後に、先ほど取り出したlength個の要素を挿入する。

解法

  • n=1の場合
    • 0回ですね
  • n=2の場合
    • 1回ですね

n>=3の場合、必ずn/2+1回で降順にできます。具体例を見ていただければ、わかりやすいです。

  • n=5（奇数）の場合
    • 1 2 3 4 5 -> 3 4 1 2 5
    • 3 4 1 2 5 -> 3 2 5 4 1
    • 3 2 5 4 1 -> 5 4 3 2 1
  • n=6（偶数）の場合
    • 1 2 3 4 5 6 -> 3 4 1 2 5 6
    • 3 4 1 2 5 6 -> 3 2 5 4 1 6
    • 3 2 5 4 1 6 -> 3 2 1 6 5 4
    • 3 2 1 6 5 4 -> 6 5 4 3 2 1

つまり、n/2以下の要素の降順を左側に寄せて、n/2より大きい要素の降順を右側に寄せるように操作しています。そして、最後に右半分を一番左に挿入してやればいいわけです。

プログラム

#include <iostream>
using namespace std;

int main(){
  int n;

  while(cin >> n){
    if(n == 1){
      cout << 0 << endl;
      continue;
    }
    if(n == 2){
      cout << "1" << endl;
      cout << "1 1 1" << endl;
      continue;
    }

    cout << n / 2 + 1 << endl;

    for(int i = 1; i <= n / 2; i++){
      cout <<  (n - 1) / 2 + i << " " << 2 << " " << i - 1 << endl;
    }
    cout << n / 2 + 1 << " " << n / 2 << " " << 0 << endl;
  }
}