/*
2002/05 Ultimate Instant Insanity
coded by Isaku WADA
 ┌────────────────────────────┐
 │ Fig.1のように,立方体の展開図がある。各面には色が塗っ│
 │てあり,Rは赤,Gは緑,Bは青,Yは黄,Wは白である。こ│
 │れを組み立てた5つの立方体を,Fig.2のように一直線に並べ│
 │る。このとき,5つの正方形が並んだ面が4面できることにな│
 │るが,それぞれの面にすべての色が出現するようにしたい。何│
 │通りの並べ方があるか。ただし,全体を回転したり,立方体の│
 │順番を入れ替えたものは別の解とはしない。        │
 │                            │
 │Fig.1 立方体の展開図      Fig.2 一直線に並べる│
 │                            │
 │RYB B RGY Y WYB    省略       │
 │ G  Y  G  B  R              │
 │ R  G  B  B  G              │
 │ W YRW W GWR W              │
 │                            │
 └────────────────────────────┘

 ┌─────────────────────┐
 │解答:3通り               │
 │                     │
 │ RYB RWY WGG WRB GBY │
 │  G   B   R   Y   W  │
 │  R   Y   B   G   W  │
 │  W   G   Y   B   R  │
 │                     │
 │ YBR YRW GGB GWR BYW │
 │  G   B   R   Y   W  │
 │  R   Y   W   B   G  │
 │  W   G   Y   B   R  │
 │                     │
 │ GBW GRB RGY BWY WYR │
 │  R   Y   B   G   W  │
 │  R   Y   W   B   G  │
 │  Y   W   G   R   B  │
 │                     │
 └─────────────────────┘

 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00098 秒│ 36864 byte │
 │Borland C++ 5.5 for Win32  │0.00171 秒│ 53760 byte │
 │gcc-2.953(djgpp)      │0.00104 秒│ 109851 byte │
 │gcc-2.953(cygwin)      │0.00156 秒│ 372414 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00209 秒│ 13608 byte │
 │Turbo C Ver 1.5(small model)│0.00182 秒│ 10986 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium!!! 550 MHz │   OS:Windows 98   │
 └──────────────┴─────────────┘

 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │ここでは、5つの立方体を並べた棒を横向きに置いたとして説明し│
 │ます。各立方体が持つ6つの面について、配列での位置と、空間上│
 │での位置との対応を、0:上、1:手前、2:下、3:奥、4:左、  │
 │5:右とします。左と右を軸とし、残りの4つの側面をリングとみ │
 │なし、左から見て時計回りに並べました。           │
 │                              │
 │配列color[0〜4][0〜5]には、問題文の展開図から、色が設定され │
 │ます。配列pos[0〜5][0〜5]には、6つの面から左の面を選んだ場 │
 │合に、空間上での位置がどの位置に変化するかの対応関係が設定さ│
 │れます。                          │
 │                              │
 │入れ替えた解を排除するために、立方体の順序は展開図の通りに固│
 │定します。また、回転した解を排除するために、一番左の立方体の│
 │置き方は3方向の軸について繰り返すのみとし、回転はしません。│
 │そして、pos[0,2,4][0〜5]のように偶数面のみを使い、     │
 │color[0][0〜5]を経由して結果の配列x[0][0〜5]に記録します。 │
 │                              │
 │残りの4つの立方体の置き方については、まず、6つの面から左の│
 │面を選びます。そして、その6通りそれぞれについて、左右を除く│
 │4つの側面を反時計回りに4回回転させます。つまり、合計24通│
 │りの置き方を試行します。そして、試行ごとに新しい立方体の側面│
 │が棒の他の側面と重複していないかどうか調べます。重複していな│
 │ければ、結果の配列x[1〜4][0〜5]にどこが何色になったかを記録 │
 │して、次の立方体を置きます。そして、5つの立方体を置くことが│
 │できたら、結果の配列x[0〜4][0〜5]を表示します。       │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │解答を見て気がついたことは、全ての立方体の全ての面が、ちょう│
 │ど1回ずつ、軸になって隠れることです。これが、Ultimateといわ│
 │れる理由ではないでしょうか。                │
 └──────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum { R,G,B,Y,W };

/* 5つの立方体を並べた棒を横向きに置いたとする。
  各立方体が持つ6つの面について、配列での位置と、実際の空間上での位
  置との対応を、0:上、1:手前、2:下、3:奥、4:左、5:右とする。*/

/*┌──────────────┐
 │元のデータ(5個の立方体) 。 │
 └──────────────┘*/
int color[5][6] = { { Y,G,R,W,R,B }, { B,Y,G,R,Y,W },
   { G,G,B,W,R,Y }, { Y,B,B,W,G,R }, { Y,R,G,W,W,B } };

/*┌──────────────────────────┐
 │立方体の向きを変えて、軸になる面を変えた時の対応表。│
 │3方向の軸に表裏の2を掛けて6通りある。      │
 └──────────────────────────┘*/
int pos[6][6] = {
  { 0,1,2,3,4,5 }, { 3,2,1,0,5,4 }, { 5,1,4,3,0,2 },
  { 3,4,1,5,2,0 }, { 5,2,4,0,1,3 }, { 0,4,2,5,3,1 } };

/*┌───────────────┐
 │実行時の5つの立方体の置き方。│
 └───────────────┘*/
int x[5][6];

/*┌────────┐
 │結果を表示する。│
 └────────┘*/
void Print(void)
{
    int i,j; static char s[]="RGBYW";

    for (i=0;i<5;i++)
       printf(" %.2s%.2s%.2s",s+x[i][4]*2,s+x[i][0]*2,s+x[i][5]*2);
    printf("\n");
    for (j=1;j<4;j++) {
        for (i=0;i<5;i++) printf("  %.2s ",s+x[i][j]*2);
        printf("\n");
    }
    printf("\n");
}

/*┌─────────────────────┐
 │立方体をひとつ置き、各面がだぶらなければ、│
 │次を再帰呼び出しして置いてゆく。     │
 └─────────────────────┘*/
void Sub(int level)
{
    int shaft,angle,i,ring[4];

    if (level==5) { Print(); return; }
    for (shaft=0;shaft<6;shaft++) {
        x[level][4]=color[level][pos[shaft][4]];
        x[level][5]=color[level][pos[shaft][5]];
        for (i=0;i<4;i++)
            ring[i]=color[level][pos[shaft][i]];
        for (angle=0;angle<4;angle++) {
            for (i=0;i<4;i++) {
                int k=ring[(i+angle)&3],j;
                for (j=0;j<level;j++) if (x[j][i]==k) break;
                if (j<level) break;
            }
            if (i==4) {
                for (i=0;i<4;i++) x[level][i]=ring[(i+angle)&3];
                Sub(level+1);
            }
        }
    }
}

/*┌─────────────────────┐
 │一番左の立方体を置き、Sub(1) を呼び出す。 │
 └─────────────────────┘*/
void Solve(void)
{
    int shaft,i;

    for (shaft=0;shaft<6;shaft+=2) {
        for (i=0;i<6;i++) x[0][i]=color[0][pos[shaft][i]];
        Sub(1);
    }
}

/*┌────────────────────┐
 │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 0;
}