/*
2000/05 ボールピラミッド
coded by Isaku WADA
 ┌────────────────────────────┐
 │ 同じ大きさの玉を20個用意し,それを接着してFig. 1のよう│
 │な6つのピースを作る。これを組み合わせてFig. 2のようなピ │
 │ラミッド(厳密には,ピラミッドは底面が正方形なので,これ │
 │は正四面体)を完成させてほしい。何通りの組み方があるか。 │
 │                            │
 │Fig.1                          │
 │A    B○  C ○ D   E○ F       │
 │○○○○ ○○○ ○○○ ○○○ ○○ ○○      │
 │                            │
 │Fig.2                          │
 │  ○   ○  ○  ○                │
 │ ○○  ○○ ○○                  │
 │ ○○○ ○○○                     │
 │○○○○                        │
 └────────────────────────────┘
 ┌─────────────────────────┐
 │・プログラムの説明                │
 │                         │
 │ピラミッドの状態は、長さ20の文字配列で表す。  │
 │配列での位置とピラミッドの対応は以下のとおり。  │
 │  H   N  Q  R             │
 │ FG  LM OP               │
 │ CDE IJK                  │
 │◎@AB                     │
 │                         │
 │ピラミッドの中には、長さが4の直線と、      │
 │3×2の長方形がそれぞれ6個存在する。      │
 │                         │
 │まず回転したものと左右相称なものを無視するために、│
 │ ピースCを[  K]              │
 │      [CDE]              │
 │に限定したピラミッドから探索を開始する。     │
 │次に、各々の長方形に2通りの方法でピースBを置く。│
 │次に、各々の長方形に2通りの方法でピースDを置き、│
 │さらに、各々の直線に2通りの方法でピースDを置く。│
 │次に、各々の長方形に8通りの方法でピースEを置く。│
 │最後に、空いているボールを2つ求め隣接行列により、│
 │隣どうしならピースFを置き、ピラミッドを表示する。│
 └─────────────────────────┘
 ┌──────────────────────────┐
 │・感想                       │
 │                          │
 │最初に問題を見たときは、ピースの角度が60度でなく、│
 │全て90度だったので、出題ミスかなと思いました。  │
 │何日かして、問題を読み直し、ピンポン玉を21個買い、│
 │実際にボールピラミッドを作ってみて初めて、     │
 │解けることがわかりました。立体の問題の楽しさと   │
 │難しさを思い知らされました。            │
 └──────────────────────────┘
*/

#include <stdio.h>
#include <time.h>
/*
 * clock()
 *
 * clock() をサポートしない MS-DOS コンパイラ用の自前の clock()
 * LSI C-86 試食版でも 1/1000 秒単位の経過時間を返すようになる
 * Visual C++、Borland C++ Builder、UNIX などでは自動的に無視される
 *
 * 最初に clock() を呼び出すと必ず0を返す。
 * 2回目以降は、最初の呼び出しからの経過時間を 1/1000 秒単位で返す
 * 経過時間が24日以上になると−1を返す
 * 閏年も考慮に入れている
 */
#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)
{
    static int day[12]={0,31,59,90,120,151,181,212,243,273,304,334};
    union REGS t,d; static long Date0=0,Time0=0; long Time1,Date1;

    t.h.ah=0x2c; d.h.ah=0x2a;
    intdos(&t,&t); intdos(&d,&d);
    Time1=t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
    Date1=d.x.cx*365L+d.x.cx/4+day[d.h.dh-1]+d.h.dl;
    if ((d.x.cx%4)==0&&d.h.dh<=2) Date1--;
    if (Date0==0)  { Date0=Date1; Time0=Time1; return 0; }
    if (Date1-Date0>=24) return-1;
    return(Date1-Date0)*86400000L+Time1-Time0;
}
#endif

#define A 1
#define B 2
#define C 3
#define D 4
#define E 5
#define F 6

char Map[20];     /* ピラミッドの状態 */
char NumOfResult; /* 組み方の総数 */

/*┌────────────────┐
 │ピラミッド中の長さ4の直線の位置│
 └────────────────┘*/
const char Line[6][4]=
{{0, 1, 2, 3},{0, 4, 7, 9},{3, 6, 8, 9},
 {0,10,16,19},{3,12,17,19},{9,15,18,19}};

/*┌─────────────────┐
 │ピラミッド中の3×2の長方形の位置│
 └─────────────────┘*/
const char Rect[6][6]=
{{4,5,6,10,11,12},{7,13,16,8,14,17},{1, 5, 8,10,13,15},
 {7,5,2,15,14,12},{4,13,18,1,11,17},{2,11,16, 6,14,18}};

/*┌─────────────────────┐
 │2つのボールが隣り合っていれば1(隣接行列)│
 └─────────────────────┘*/
const char AdjacentMatrix[20][20]=
{/* 0*/{0,1,0,0,1, 0,0,0,0,0, 1,0,0,0,0, 0,0,0,0,0},
 /* 1*/{1,0,1,0,1, 1,0,0,0,0, 1,1,0,0,0, 0,0,0,0,0},
 /* 2*/{0,1,0,1,0, 1,1,0,0,0, 0,1,1,0,0, 0,0,0,0,0},
 /* 3*/{0,0,1,0,0, 0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,0},
 /* 4*/{1,1,0,0,0, 1,0,1,0,0, 1,0,0,1,0, 0,0,0,0,0},
 /* 5*/{0,1,1,0,1, 0,1,1,1,0, 0,1,0,1,1, 0,0,0,0,0},
 /* 6*/{0,0,1,1,0, 1,0,0,1,0, 0,0,1,0,1, 0,0,0,0,0},
 /* 7*/{0,0,0,0,1, 1,0,0,1,1, 0,0,0,1,0, 1,0,0,0,0},
 /* 8*/{0,0,0,0,0, 1,1,1,0,1, 0,0,0,0,1, 1,0,0,0,0},
 /* 9*/{0,0,0,0,0, 0,0,1,1,0, 0,0,0,0,0, 1,0,0,0,0},
 /*10*/{1,1,0,0,1, 0,0,0,0,0, 0,1,0,1,0, 0,1,0,0,0},
 /*11*/{0,1,1,0,0, 1,0,0,0,0, 1,0,1,1,1, 0,1,1,0,0},
 /*12*/{0,0,1,1,0, 0,1,0,0,0, 0,1,0,0,1, 0,0,1,0,0},
 /*13*/{0,0,0,0,1, 1,0,1,0,0, 1,1,0,0,1, 1,1,0,1,0},
 /*14*/{0,0,0,0,0, 1,1,0,1,0, 0,1,1,1,0, 1,0,1,1,0},
 /*15*/{0,0,0,0,0, 0,0,1,1,1, 0,0,0,1,1, 0,0,0,1,0},
 /*16*/{0,0,0,0,0, 0,0,0,0,0, 1,1,0,1,0, 0,0,1,1,1},
 /*17*/{0,0,0,0,0, 0,0,0,0,0, 0,1,1,0,1, 0,1,0,1,1},
 /*18*/{0,0,0,0,0, 0,0,0,0,0, 0,0,0,1,1, 1,1,1,0,1},
 /*19*/{0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,1,1,1,0}};

/*┌────────┐
 │ピラミッドの表示│
 └────────┘*/
void PrintPyramid(void)
{
    /* 与えられた位置のボールがどのピースかを全角で表示する */
    const char*v[]={"Z","A","B","C","D","E","F"};
    const char f1[]="   %s        %s      %s    %s\n";
    const char f2[]="  %s%s      %s%s    %s%s\n";
    const char f3[]=" %s%s%s    %s%s%s\n";
    const char f4[]="%s%s%s%s\n\n";
    char*m=Map;
    printf("組み方 %d\n", ++NumOfResult );
    printf(f1,v[m[9]],v[m[15]],v[m[18]],v[m[19]]);
    printf(f2,v[m[7]],v[m[8]], v[m[13]],v[m[14]],v[m[16]],v[m[17]]);
    printf(f3,v[m[4]],v[m[5]], v[m[6]], v[m[10]],v[m[11]],v[m[12]]);
    printf(f4,v[m[0]],v[m[1]], v[m[2]], v[m[3]]);
}


/*┌───────────────────────┐
 │ピースFを置き、ピラミッドが完成したら表示する│
 └───────────────────────┘*/
void PutPieceF(void)
{
    char n,m,i;
    for (i=0;i<20;i++) if (Map[i]==0) { n=i; break; }
    for (i++;i<20;i++) if (Map[i]==0) { m=i; break; }
    if (AdjacentMatrix[n][m]) {
        Map[n]=Map[m]=F;
        PrintPyramid();
        Map[n]=Map[m]=0;
    }
}

/*┌─────────────────────┐
 │ピースEを置くことができたらピースFに進む│
 └─────────────────────┘*/
void PutPieceE(void)
{
    /* 長方形中のピースEの位置 */
    const char PosE[8][3]={{0,1,3},{1,2,4},{1,3,4},{2,4,5},
                           {0,1,4},{1,2,5},{0,3,4},{1,4,5}};
    char n,m,i;
    for (n=0;n<6;n++) for (m=0;m<8;m++) {
        for (i=0;i<3;i++) if (Map[Rect[n][PosE[m][i]]]) break;
        if (i==3) {
            for (i=0;i<3;i++) Map[Rect[n][PosE[m][i]]]=E;
            PutPieceF();
            for (i=0;i<3;i++) Map[Rect[n][PosE[m][i]]]=0;
        }
    }
}

/*┌─────────────────────┐
 │ピースDを置くことができたらピースEに進む│
 └─────────────────────┘*/
void PutPieceD(void)
{
    /* 長方形中のピースDの位置 */
    const char PosD[2][3]={{0,1,2},{3,4,5}};
    char n,m,i;
    for (n=0;n<6;n++) for (m=0;m<2;m++) {
        for (i=0;i<3;i++) if (Map[Rect[n][PosD[m][i]]]) break;
        if (i==3) {
            for (i=0;i<3;i++) Map[Rect[n][PosD[m][i]]]=D;
            PutPieceE();
            for (i=0;i<3;i++) Map[Rect[n][PosD[m][i]]]=0;
        }
    }
    for (n=0;n<6;n++) for (m=0;m<2;m++) {
        for (i=0;i<3;i++) if (Map[Line[n][m+i]]) break;
        if (i==3) {
            for (i=0;i<3;i++) Map[Line[n][m+i]]=D;
            PutPieceE();
            for (i=0;i<3;i++) Map[Line[n][m+i]]=0;
        }
    }
}

/*┌─────────────────────┐
 │ピースBを置くことができたらピースDに進む│
 └─────────────────────┘*/
void PutPieceB(void)
{
    /* 長方形中のピースBの位置 */
    const char PosB[2][4]={{0,1,2,4},{1,3,4,5}};
    char n,m,i;
    for (n=0;n<6;n++) for (m=0;m<2;m++) {
        for (i=0;i<4;i++) if (Map[Rect[n][PosB[m][i]]]) break;
        if (i==4) {
            for (i=0;i<4;i++) Map[Rect[n][PosB[m][i]]]=B;
            PutPieceD();
            for (i=0;i<4;i++) Map[Rect[n][PosB[m][i]]]=0;
        }
    }
}

/*┌─────────────────────┐
 │ピースAを置くことができたらピースBに進む│
 └─────────────────────┘*/
void PutPieceA(void)
{
    char n,i;
    for (n=0;n<6;n++) {
        for (i=0;i<4;i++) if (Map[Line[n][i]]) break;
        if (i==4) {
            for (i=0;i<4;i++) Map[Line[n][i]]=A;
            PutPieceB();
            for (i=0;i<4;i++) Map[Line[n][i]]=0;
        }
    }
}

/*┌───────────────────┐
 │ピースCを置く。置いたらピースBに進む│
 └───────────────────┘*/
void main(void)
{
    /* ピラミッド中のピースCの位置 */
    const char PosC[4]={4,5,6,12};
    char i; double StartTime=clock();
    for (i=0;i<4;i++) Map[PosC[i]]=C;
    PutPieceA();
    printf("組み方の総数:%d通り\n",NumOfResult);
    printf("実行時間:%f秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
}