/*
 *  mamako1.c --
 *
 *
 * ver 0.01                   2007.12.28. H.Hasegawa
 */

/*
 * 問１：トランプ５２枚を揃えて手に持つ。そのカードの一番上の１枚を捨てて次の１枚を残りのカードの
 * 一番下にもってくる、という作業を繰り返す。このとき、最後まで残っているのは最初の並びの上から何番目のカードか？
 *
 * 問２：上記の操作の結果、捨てられたカードを順に並べる。これを継子立てシャッフルと呼ぶ。（by Tessyさん）
 *　このシャッフルで何回操作したら元に戻るかを調べたい。
 *
 */

#include <stdio.h>

typedef struct Card{
	int num;
	struct Card *next;
} Card;


Card *Current_Head;
Card *Current_Tail;

Card *Next_Head;
Card *Next_Tail;

int CardNum;		// デッキのカードの枚数

/*
 * 初期化処理：カードの枚数を受け取って、リストを作る
 */
void init(int card_num) {
	int   i;
	Card *current,*next;

	CardNum = card_num;		// グローバル変数にカードの枚数を代入
	current = Current_Head = (Card *)malloc(sizeof(Card));
	current->num=0;

	for ( i=1 ; i < card_num ; i++ ) {
		next = (Card *)malloc(sizeof(Card));
		current->next = next;
		current = next;
		current->num = i;
	}
	current->next = (Card *)NULL;
	Current_Tail = current;
	Next_Head = Next_Tail = (Card *)NULL;
}


/*
 * Current_Head のリストの先頭のカードを最後尾に移す。
 */
void tailing_card()
{
	Card *p;

	p = Current_Head;
	if ( p == (Card *)NULL ) {		// リストが空ならなにもしない
		return;
	}

	if ( p->next == (Card *)NULL ) {	// リストの要素が１つなら何もしない
		return;
	}

	Current_Head = p->next;			// 次のカードがリストの先頭になる
	Current_Tail->next = p;			// p を最後尾の next につなぐ
	p->next = (Card *)NULL;			// p の next を NULL にする
	Current_Tail = p;				// 現在の最後尾を p にする
}


/*
 * Current_Head の先頭のカードを Next_Tail に移す
 */
void move_card()
{
	Card *p;

	p = Current_Head;
	if ( p == (Card *)NULL ) {		// リストが空ならなにもしない
		return;
	}

	Current_Head = p->next;
	Next_Tail->next = p;
	Next_Tail = p;
	p->next = (Card *)NULL;
}

/*
 * シャッフル処理：
 * 1). Current_Head から１つ取って、Next_Tail に移す。
 * 2). Current_Head から１つ取って、Current_Tail につなぐ。
 * これをCurrent_Head = Current_Tail = NULL になるまで続ける。
 *
 * この処理は本当は再帰で書くとかっこいい
 */
void shuffle()
{
	int i;
	Card *p;

	Next_Head = Next_Tail = Current_Head;
	if ( Current_Head == (Card *)NULL ) {		// リストに要素が１つもなかった場合
		return;
	}

	Current_Head = Current_Head->next;
	if ( Current_Head == (Card *)NULL ) {		// リストに要素が１つしかなかった場合
		return;
	}
	Next_Tail->next = (Card *)NULL;

	tailing_card();								// Currentのリストの先頭のカードを最後尾に移動する関数

	// 以下は、リストに要素が２つ以上ある（カードの枚数が２枚以上）の場合。
	for ( i=1 ; i < CardNum ; i++ ) {
		move_card();
		tailing_card();
	}
}

/*
 * Nextのリストを調べて、元通りに復元しているか確認する
 *
 * 揃っていたら1、揃っていなければ 0 を返す
 */
int check()
{
	int i;
	Card *p;

	p=Next_Head;
	for ( i=0 ; i < CardNum ; i++ ) {
		if ( p==(Card *)NULL ) return 0;		// そもそも数が合わない
		if ( p->num != i ) return 0;
		p=p->next;
	}
	return 1;
}


/*
 *	Next を Current にする
 */
void exchange()
{
	Current_Head = Next_Head;
	Current_Tail = Next_Tail;

	Next_Head = Next_Tail = (Card *)NULL;
}


/*
 *
 */
int search(int num)
{
	int c;			// counter
	int result;

	init(num);

	for ( c=1 ; ; c++ ) {
		shuffle();
		result = check();
		if ( result == 1 ) {
			return c;
		}
		exchange();
	}
	return 0;
}


int main(int argc, char **argv)
{
	int num;
	int result;

	if ( argc != 2 ) {
		printf("usage    : Prompt> mamako1.exe card_num\n");
		printf("exsample : Prompt> mamako 52\n");
		return 1;
	}

	num = atoi(argv[1]);
	if ( num < 1 ) {
		printf("usage    : Prompt> mamako1.exe card_num\n");
		printf("exsample : Prompt> mamako 52\n");
		return 1;
	}

	result = search(num);

	printf("%5d : %5d\n",num,result);

	return 0;
}