/*
2005/2 アンカーパチンコ
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ ちょっと変わったパチンコの問題。Fig.1-(a)のような形をし│
 │たもので、上部の穴から玉を落とすようになっている。8個ある│
 │「イカリ」みたいなものは、Fig.2のように、左右にカタカタと│
 │倒れる。さて、どの穴でもよいのだが、例えばBの穴から玉を落│
 │とすと、玉は2、4、6番のイカリを次々と反対側に倒しながら│
 │下に落ちていき、その結果Fig.1-(b)のような状態になる。次に│
 │またBの穴から玉を落とすと、Fig.1-(c)のようになる。同じ穴│
 │に続けて落としても、すぐには元の状態に戻らないのである。 │
 │ では、このように玉を1つずつ落として、Fig.1-(a)の状態か│
 │ら、すべてのイカリを反対側に倒した状態にするには、どこに何│
 │回玉を落とす必要があるだろうか。また、同様にFig.3の台では│
 │どうだろうか。                      │
 │ なお、左右の端を落ちる玉は、Fig.1-(d)のように側面の壁で│
 │戻されて、真下のイカリ(この場合6番のイカリ)を動かすように│
 │なっている。                       │
 │                             │
 │  Fig.1 アンカーパチンコの例             │
 │    (a)        (b)             │
 │ ┏━A━B━C━┓ ┏━ ━↓━ ━┓         │
 │ ┃       ┃ ┃   ←   ┃         │
 │ ┃ \ \ \ ┃ ┃ \ / \ ┃         │
 │ ┃ 1 2 3 ┃ ┃ 1↓2 3 ┃         │
 │ ┃       ┃ ┃  ←    ┃         │
 │ ┗┓ \ \ ┏┛ ┗┓ / \ ┏┛         │
 │ ┏┛ 4 5 ┗┓ ┏┛↓4 5 ┗┓         │
 │ ┃       ┃ ┃ ←     ┃         │
 │ ┃ \ \ \ ┃ ┃ / \ \ ┃         │
 │ ┃ 6 7 8 ┃ ┃↓6 7 8 ┃         │
 │ ┗━━━ ━━━┛ ┗━━━ ━━━┛         │
 │                             │
 │    (c)        (d)             │
 │ ┏━ ━↓━ ━┓ ┏━↓━ ━ ━┓         │
 │ ┃   →   ┃ ┃ ←     ┃         │
 │ ┃ \ \ \ ┃ ┃ / \ \ ┃         │
 │ ┃ 1 2↓3 ┃ ┃↓1 2 3 ┃         │
 │ ┃    ←  ┃ ┃→      ┃         │
 │ ┗┓ / / ┏┛ ┗┓ \ \ ┏┛         │
 │ ┏┛ 4↓5 ┗┓ ┏┛↓4 5 ┗┓         │
 │ ┃   ←   ┃ ┃ ←     ┃         │
 │ ┃ / / \ ┃ ┃ / \ \ ┃         │
 │ ┃ 6↓7 8 ┃ ┃↓6 7 8 ┃         │
 │ ┗━━━ ━━━┛ ┗━━━ ━━━┛         │
 │                             │
 │ Fig.2 イカリの形状                  │
 │                             │
 │    ←→ /  \ ←→               │
 │ │\   /    \   /│            │
 │ │ \ /      \ / │            │
 │ │  ●        ●  │            │
 │ │   \      /   │            │
 │ │    \    /    │            │
 │ └─────    ─────┘            │
 │                             │
 │ Fig.3 もう1つの台                  │
 │ ┏━A━B━C━D━┓                 │
 │ ┃         ┃                 │
 │ ┃ \ \ \ \ ┃                 │
 │ ┃ 1 2 3 4 ┃                 │
 │ ┃         ┃                 │
 │ ┗┓ \ \ \ ┏┛                 │
 │ ┏┛ 5 6 7 ┗┓                 │
 │ ┃         ┃                 │
 │ ┃ \ \ \ \ ┃                 │
 │ ┃ 8 9 10 11 ┃                 │
 │ ┃         ┃                 │
 │ ┗┓ \ \ \ ┏┛                 │
 │ ┏┛ 12 13 14 ┗┓                 │
 │ ┃         ┃                 │
 │ ┃ \ \ \ \ ┃                 │
 │ ┃ 15 16 17 18 ┃                 │
 │ ┗━━━━ ━━━━┛                 │
 └─────────────────────────────┘

 ┌─────────────────────────────┐
 │解答:                          │
 │小さな台:Aが1回、Bが5回、Cが1回。         │
 │大きな台:Aが13回、Bが9回、Cが5回、Dが1回。    │
 └─────────────────────────────┘

 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 再帰呼び出しをした、深さ優先探索で解きました。イカリの状│
 │態は1つ1ビットで表しました。右を向いていれば0で、左を向│
 │いていれば1です。台は8個あるいは18個のイカリを持ってい│
 │るので、全てのイカリの状態をlong型整数1つで表しました。初│
 │期状態は全てのイカリが右を向いているので0です。     │
 │ どの穴から何回玉を落とすかが決まれば、順番はどのようにし│
 │ても同じ結果になるので、深さ優先探索でも十分速くなりました│
 │。                            │
 │ プログラムは落とす玉の数を、穴と同じ数から始め、徐々に増│
 │やしてゆきます。落とす玉の数が決まったら、Aから順に何回落│
 │とすかを決めます。終了状態になったら計算を終えます。   │
 ├─────────────────────────────┤
 │                             │
 │・感想                          │
 │                             │
 │ 16ピットスモールモデルで解くのには、工夫が必要でした。│
 └─────────────────────────────┘

 ┌───────────────┬──────┬──────┐
 │コンパイラ          │小さな台(秒)│大きな台(秒)│
 ├───────────────┼──────┼──────┤
 │Visual Studio C++ 6.0      │ 0.000001359│ 0.000703 │
 │Visual Studio C++ 2003      │ 0.000001296│ 0.000687 │
 │Borland C++ 5.5.1 for Win32  │ 0.000001734│ 0.000875 │
 │gcc-2.953(djgpp)       │ 0.000001264│ 0.000879 │
 │gcc-3.3.3(cygwin)       │ 0.000001000│ 0.000844 │
 │LSI C-86 Ver 3.30 試食版   │ 0.000006700│ 0.005110  │
 │Turbo C Ver 1.5(small model) │ 0.000034490│ 0.019770  │
 ├───────────────┼──────┴──────┤
 │ CPU:Pentium4 2.52GHz  │ OS:Windows XP     │
 └───────────────┴─────────────┘
*/

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

/*┌─────┐
 │変数の宣言│
 └─────┘*/
 /* イカリの繋がりかた。Next1が小さな台用、Next2が大きな台用 */
 /* 0 ならば、もう下にイカリはない */
int Next1[][2]=
{{0,0},{6,4},{4,5},{5,8},{6,7},{7,8},{0,0},{0,0},{0,0}};

int Next2[][2]=
{{0,0},{8,5},{5,6},{6,7},{7,11},{8,9},{9,10},{10,11},
 {15,12},{12,13},{13,14},{14,18},{15,16},{16,17},
 {17,18},{0,0},{0,0},{0,0},{0,0}};

int PrintMode;   /* 解を表示するなら1 */
int FindFlag;    /* 解が見つかったら1 */
int NumOfHoles;  /* 台の上部の穴の数 */
int NumOfAnch;   /* イカリの数 */
int NumOfDrop;   /* 落とした回数 */
int(*Next)[2];   /* イカリの繋がりかた。Next1かNext2のいずれか */
long Goal;       /* 終了状態 */
int Result[100]; /* 玉を落とした穴の結果を記録する */

/*┌──────────┐
 │解を見つけた時の処理│
 └──────────┘*/
void FindProc(void)
{
    int j,k,count;

    FindFlag=1;
    if (PrintMode==0) return;
    for (j=1;j<=NumOfHoles;j++) {
        for (count=k=0;k<NumOfDrop;k++) if (Result[k]==j) count++;
        printf("%c:%2d   "," ABCD"[j],count);
    }
    printf("total:%d\n",NumOfDrop);
}

/*┌────────────────┐
 │穴から玉を落として次の状態を得る│
 └────────────────┘*/
long Drop(long stat,int hole)
{
    int i;

    for (i=hole;i;i=Next[i][(stat&(1L<<i))==0]) stat^=1L<<i;
    return stat;
}

/*┌───────────────────┐
 │再帰呼び出しをしながら玉を落としてゆく│
 └───────────────────┘*/
void Sub(int lv,int prev,long x)
{
    if (lv==NumOfDrop-1) {
        if (Drop(x,NumOfHoles)==Goal) FindProc();
        return;
    }
    Result[lv]=prev; Sub(lv+1,prev,Drop(x,prev));
    /* 既に最後尾だったり、偶数回連続している時は次に進めない */
    if (prev==NumOfHoles||((prev+lv)&1)) return; else prev++;
    Result[lv]=prev; Sub(lv+1,prev,Drop(x,prev));
}

/*┌────────┐
 │パズルを1回解く│
 └────────┘*/
void Solve(long num)
{
    int i; char buf[100];

    PrintMode=(num==0); FindFlag=0;
    for (i=1;i<=NumOfAnch;i++) Goal|=1L<<i; /* 終了状態を求める */
    Result[0]=1;              /* 最初は必ずAの穴から玉を落とす */
    for (NumOfDrop=NumOfHoles;NumOfDrop<100;NumOfDrop+=2) {
        Result[NumOfDrop-1]=NumOfHoles; /* 最後は右の穴から落とす */
        Sub(1,1,Drop(0,1));
        if (FindFlag) return;
    }
    printf("解がない > "); fgets(buf,sizeof buf,stdin); exit(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

/*┌───────────────────────┐
 │パラメータを指定して、繰り返し解いた時間を計る│
 └───────────────────────┘*/
void Test(int holes,int anch,int(*next)[2],long def)
{
    double lap; long i,num; char buf[100];

    NumOfHoles=holes; NumOfAnch=anch; Next=next;
    printf("\n穴の数が %d の場合を計算します。  ",holes);
    printf("繰り返し数 (%ld) ? > ",def);
    fgets(buf,sizeof buf,stdin);
    if ((num=atol(buf))==0) num=def;
    lap=clock();
    for (i=0;i<num;i++) Solve(i);
    lap=(clock()-lap)/CLOCKS_PER_SEC;
    printf("計算時間 %.3f 秒 平均 %.9f 秒\n",lap,lap/num);
    printf("HIT ENTER > "); fgets(buf,sizeof buf,stdin);
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{ Test(3,8,Next1,1000000L); Test(4,18,Next2,1000); return 0; }