POJ 3032 Card Trick

問題

マジシャンが1からnまでの数字が書かれたn枚のカードを次のような手順で場にディールしていく。

1回目はカードデッキの一番上の1枚をデッキの一番下に移し、新たに一番上になった一枚をディール。
2回目はカードデッキの一番上の2枚をデッキの一番下に移し、新たに一番上になった一枚をディール。
・
・
n回目はカードデッキの一番上のn枚をデッキの一番下に移し、新たに一番上になった一枚をディール。

こうしてディールされたカードの数字が1,2,3,...,nの順になっていた場合、ディール開始前のデッキのカードの順序を返せ。

やりかた

カードがデッキに無限枚あった場合を想定すると、1回目は上から2枚目がデッキにディールされ、2回目は次に一番上になるカードから3枚目、3回目は次に一番上になるカードから4枚目、というようにn回目は上からn+1枚目がディールされる。
これを実装すればいい。コード上ではデッキを配列に見立て、頭から2個目を1、そこから3個目を2というように番号付けしていけばいい。ただデッキの枚数は有限なので最後まで調べきったら頭に戻るようにする。

以下ソース。

int main(int argc, char **argv){
  int n; cin >> n;
  for(int i = 0; i < n; i++){
    int m; cin >> m;
    vector<int> t(m, -1);//デッキに出されていないカードは-1にしておく

    int idx = 0;//今見ている配列の場所
    for(int j = 1; j <= m; j++){
      int T = j + 1;//j回目に出されるカードはデッキに残っているカードの中のj+1枚目にある
      while(1){
	if(t[idx] == -1) T--;
	if(T == 0){
	  t[idx] = j;
	  break;
	}
	idx = (idx + 1) % m;
      }
    }
    for(int j = 0; j < m; j++) cout << t[j] << " ";
    cout << endl;
  }
}