/*
2003/03 リバース・スーバリ
coded by Isaku WADA
 ┌───────────────────────────┐
 │ Fig.2の例のように,「CHAR」という文字列を逆順の│
 │「RAHC」にしたい。移動              │
 │のしかたは「左側から2文字  Fig.2 文字列     │
 │以上をそのまま裏返す」であ              │
 │る。例では,下線部を6回ひ     CHAR     │
 │っくり返して完成している。      ̄ ̄ ̄      │
 │使うアルファベットの文字の     AH⊃R     │
 │左右対称性を利用してかまわ      ̄ ̄       │
 │ないことにする。          HA⊃R     │
 │                   ̄ ̄ ̄ ̄     │
 │ では,この移動を使って何     ЯCAH     │
 │回で「CMAGAZINE」      ̄ ̄       │
 │を「ENIZAGAMC」に     ⊃RAH     │
 │できるだろうか? 最低回数      ̄ ̄ ̄ ̄     │
 │をお答えいただきたい。       HAЯC     │
 │                   ̄ ̄ ̄      │
 │   (問題提供:滝沢清氏)    RAHC     │
 │                           │
 └───────────────────────────┘
 ┌────────┐
 │解答:最低12回│
 └────────┘
┌───────────────────────────────┐
│・プログラムの説明                      │
│                               │
│まず、後ろから4手うごかしたらどうなるかを記録しておきます。こ│
│のとき、検索を高速にするためにハッシュテーブルも構成します。 │
│プログラムは1重forループ相当で探索を始め、2重、3重...そし │
│て、最終的に8重forループ相当で解答を見つけ終了します。(コーデ│
│ィング上は再帰呼び出しを使ったforループです)。        │
│                               │
│下準備として、A〜Zまでを0〜25の数字に割りあて、裏返しに │
│なって読めなくなった文字b〜zを、さらに26から40の数字に │
│割りあてます。画面に表示する場合は、通常のA〜Zは大文字、裏 │
│返しのb〜zは小文字を使います。プログラムは高速化のため、例 │
│えばA→A,B→b,b→Bという変換を行うテーブルconvを作成し │
│ておきます。これは、メインループで裏返す時に使います。    │
│                               │
│hist[]は、裏返しにする右位置を8手について記録します。    │
│hist[]の各々の要素は8重forループの制御変数と同じ役割をし   │
│ます。                            │
├───────────────────────────────┤
│・感想                            │
│                               │
│最初はハッシングを使った幅優先探索で約20秒で解いていました。│
│しかし、メモリを130メガバイト以上消費するプログラムになり、│
│古い計算機や16ビットのコンパイラでは解けないのでやめました。│
└───────────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ          │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0    │ 0.08921秒│  36864 byte  │
 │Microsoft Visual C++ .NET   │ 0.07796秒│  45056 byte  │
 │Borland C++ 5.5.1 for Win32 │ 0.09891秒│  54784 byte  │
 │gcc-2.953(djgpp)            │ 0.08352秒│ 109776 byte  │
 │gcc-2.953(cygwin)           │ 0.08515秒│  21337 byte  │
 │LSI C-86 Ver 3.30 試食版  │ 1.05500秒│ 14136 byte │
 │Turbo C Ver 1.5(small model)│ 1.66500秒│ 11798 byte │
 └──────────────┴─────┴───────┘
    CPU:Pentium4 2.52GHz       OS:Windows XP
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
char Str[]="CMAGAZINE"; /* 文字列 */

/*
 BACK:後ろから記録する手数
 ※文字列が CHAR のように小さな手数で逆転するならば、
 それに合わせて小さな値にすること。
 */
#define BACK (sizeof(int)==2?4:6)
#define LEN (sizeof Str-1) /* 文字列の長さ */
#define MAX 12             /* 最大反転回数 */
char Code[42]="ABCDEFGHIJKLMNOPQRSTUVWXYZbcdefgjklnpqrsz";

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int HashSize;    /* ハッシュテーブルの大きさ */
char Conv[41];   /* 変換テーブル */
char End[LEN];   /* 終了配置 */
char*Data[BACK]; /* 後ろからの手数を記録 */
int*HashTable;   /* ハッシュテーブル */
int*HashNext;    /* 同じハッシュ値の次の要素 */

/*┌──────┐
 │メモリの確保│
 └──────┘*/
char*GetMem(unsigned a,unsigned b)
{
    char*p=calloc(a,b);

    if (p==0) {
        printf("calloc()が0を返した\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

/*┌──────┐
 │ハッシュ関数│
 └──────┘*/
int HashFunc(char*p)
{
    unsigned hash=0,i;

    for (i=0;i<LEN;i++) hash=hash*43+p[i];
    return hash%HashSize;
}

/*┌─────┐
 │解答の表示│
 └─────┘*/
void Print(char*map,int size)
{
    int i; static int step;

    if (step==-1) return;
    printf("%3d ",step++);
    for (i=0;i<LEN;i++)
        printf("%c",Code[(int)map[i]]);
    printf("\n");
    if (size) {
        printf("    ");
        for (i=0;i<=size;i++) printf("~");;
        printf("\n");
    }else
        step=-1;
}

/*┌──────────────────┐
 │メインループ(解が見つかれば1を返す)│
 └──────────────────┘*/
int Loop(int move,char*map)
{
    static int level;
    static char log[MAX-BACK][LEN]; /* 配置の記録 */
    static char hist[MAX-BACK];     /* 反転のし方の履歴 */
    int i;

    for (i=0;i<LEN;i++) log[level][i]=map[i];
    for (i=1;i<LEN;i++) {
        if (level&&i==hist[level-1]) continue;

        {
            int s,t,u,v,k;
            for (k=0;k<LEN;k++) map[k]=log[level][k];
            for (s=0,t=i;s<=t;s++,t--)
            { u=map[s]; v=map[t]; map[s]=Conv[v]; map[t]=Conv[u]; }
        }
        hist[level]=(char)i; level++;
        if (level==move) {
            int h=HashFunc(map),k,j; char*p;
            for (k=HashTable[h];k!=-1;k=HashNext[k]) {
                p=Data[BACK-1]+(unsigned)k*LEN;
                for (j=0;j<LEN;j++) if (map[j]!=p[j]) break;
                if (j==LEN) break;
            }
            if (k!=-1) { /* 終了条件 */
                /* 解答の表示 */
                for (j=0;j<move;j++) Print(log[j],hist[j]);
                for (j=BACK-1;j>=0;j--) {
                    Print(Data[j]+(unsigned)k*LEN,(k%(LEN-1))+1);
                    k/=LEN-1;
                }
                Print(End,0);
                level--; return 1;
            }
        }else if (Loop(move,map)) { level--; return 1; }
        level--;
    }
    return 0;
}

/*┌─────────────┐
 │後ろからのデータを作成する│
 └─────────────┘*/
void MakeData(char*from,int n)
{
    static int level; char*p;
    int s,t,u,v,k,h,i,j;

    for (i=0;i<LEN-1;i++) {
        k=n*(LEN-1)+i;
        p=Data[level]+(unsigned)k*LEN;
        for (j=0;j<LEN;j++) p[j]=from[j];
        for (s=0,t=i+1;s<=t;s++,t--)
        { u=p[s]; v=p[t]; p[s]=Conv[v]; p[t]=Conv[u]; }
        level++;
        if (level==BACK)
        { h=HashFunc(p); HashNext[k]=HashTable[h]; HashTable[h]=k; }
        else MakeData(p,k);
        level--;
    }
}

/*┌────────┐
 │パズルを1回解く│
 └────────┘*/
void Solve(void)
{
    char map[LEN]; /* 配置 */
    int move,i;     /* 反転回数 */

    /* 変換テーブルの作成 */
    for (i=0;i<26;i++) Conv[i]=(char)i;
    for (i=26;Code[i];i++)
    { Conv[Code[i]-'a']=(char)i; Conv[i]=(char)(Code[i]-'a'); }

    /* 終了配置の作成 */
    for (i=0;i<LEN;i++) End[LEN-1-i]=(char)(Str[i]-'A');

    HashSize=1;
    for (i=0;i<BACK;i++) Data[i]=GetMem(HashSize*=LEN-1,LEN);
    HashTable=(int*)GetMem(HashSize,sizeof(int));
    memset(HashTable,-1,HashSize*sizeof(int));
    HashNext=(int*)GetMem(HashSize,sizeof(int));
    MakeData(End,0);
    for (move=1;move<=MAX-BACK;move++) {
        /* 初期配置の作成 */
        for (i=0;i<LEN;i++) map[i]=(char)(Str[i]-'A');
        /* メインループ */
        if (Loop(move,map)) {
            free(HashNext); free(HashTable);
            for (i=BACK-1;i>=0;i--) free(Data[i]);
            return;
        }
    }
    printf("cannot solve\n"); exit(EXIT_FAILURE);
}


/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────┐
 │メイン・ルーチン│
 └────────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}