/*
2001/03 六角形の超線上
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig. 1のような六角形のマスの真ん中にコインを置く。ただ │
 │し,「どんな直線も,3枚以上のコインの中心を通ってはいけな │
 │い」という条件付きだ。最大何枚のコインを置けるだろうか。 │
 │また,その最大枚数での配置には,全体を回転した解・鏡像の │
 │解を除いて何通りあるだろうか。Fig. 2では10枚のコインが置 │
 │いてあるが,太線で示すところがマズいことになる。     │
 │                             │
 │ Fig.1六角形のマス  Fig.2直線上に並ぶ例        │
 │  ○○○○        ○●○○ /           │
 │ ○○○○○       ●○○○●            │
 │ ○○○○○○      ○○○●○●           │
 │○○○○○○○     ○○○○○○○           │
 │ ○○○○○○      ●○○○○●           │
 │ ○○○○○     / ○○●●○            │
 │  ○○○○        ●○○○            │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │\X=-3 -2 -1 0 1 2 3                 │
 │Y=┌──────────                 │
 │-3│ 0 1 2 3 * * *                 │
 │-2│ 4 5 6 7 8 * *                 │
 │-1│ 9 10 11 12 13 14 *                 │
 │ 0│15 16 17 18 19 20 21                 │
 │ 1│ * 22 23 24 25 26 27                 │
 │ 2│ * * 28 29 30 31 32                 │
 │ 3│ * * * 33 34 35 36                 │
 │    図1                        │
 │                             │
 │37個の点に対して図1のように番号をつけ、37bitの集合型の型を│
 │定義し、いくつかの集合演算を記述しました。        │
 │                             │
 │マクロID(X,Y)は図1のような(X,Y)座標から番号を返します。逆 │
 │に、配列RevX[i]は番号からX座標、配列RevY[i]は番号からY座標│
 │を返します。                       │
 │                             │
 │まず、早見表Lineを作成します。Line[i][j]は2つの点iとjに対 │
 │する、2点を結ぶ直線上にある全ての番号を含んだ集合となりま │
 │す。                           │
 │                             │
 │次に、再帰呼び出しをしながら、点0から順番にコインを置いて │
 │ゆきます。この時に、過去に置いたコインと、新しいコインの直│
 │線上にある点に、Lineを利用して印を付けます。次に置くときに│
 │は、印のない点にします。                 │
 │                             │
 │こうして、直線上に3点並ばないコインの置き方がわかります。 │
 │新しい置き方を見つけたとき、(X,Y)座標上の一次変換により、 │
 │60度の回転5回、反転を1回、さらに、60度の回転5回行って、回 │
 │転と鏡像を排除します。                  │
 │                             │
 │高速化のため、探索を開始する点は0,1,5,6,11,18 に限定しまし│
 │た。また、開始する点よりも外の点も無視することにより、さら│
 │に高速化しました。                    │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・感想                          │
 │                             │
 │集合演算を関数ではなくマクロで行うことにより、約0.58倍の時│
 │間短縮に成功しました。また、早見表を上三角行列にすることに│
 │より、LSI C試食版でも、ふたまわり大きな問題が解けるように │
 │なりました。                       │
 └─────────────────────────────┘
  Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
  スモールモデルでもN=5まで対応。それ以上は確認していない
*/

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

#define N 3 /* 六角形の1辺の長さ引く1(デフォルト3) */
            /* N=5 の時40分かかった */

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

#define HEIGHT (N*2+1)              /* 盤の高さ                */
#define NUM (HEIGHT*HEIGHT-(N+1)*N) /* マスの総数              */
#define BIT (INT_MAX==32767?16:32)  /* int のビット数          */
#define SIZE ((NUM-1)/BIT+1)        /* 集合型に必要な int の数 */
#define ID(X,Y) (id[(Y)+N][(X)+N])  /* 座標から番号へ変換する  */
#define NONE (-1)                   /* (X,Y)が外れている場合   */

/*┌─────────┐
 │集合型 set の定義 │
 └─────────┘*/
typedef int set[SIZE];

#if SIZE == 2
/*┌─────────────────────┐
 │マクロによる集合演算の実装(SIZE==2の場合) │
 └─────────────────────┘*/
#define COPY(X,Y) ((X)[0]=(Y)[0],  (X)[1]=(Y)[1] )
#define CLEAR(X)  ((X)[0]=0,       (X)[1]=0      )
#define OR(X,Y)   ((X)[0]|=(Y)[0], (X)[1]|=(Y)[1])
#define EQ(X,Y)   ((X)[0]==(Y)[0]&&(X)[1]==(Y)[1])
#define ADD(X,Y)  ((Y)>=BIT?((X)[1]|=1<<((Y)-BIT)):((X)[0]|=1<<(Y)))
#define IN(X,Y)   ((Y)>=BIT? (X)[1]&(1<<((Y)-BIT)): (X)[0]&(1<<(Y)))

#elif SIZE == 3
/*┌─────────────────────┐
 │マクロによる集合演算の実装(SIZE==3の場合) │
 └─────────────────────┘*/
#define COPY(X,Y) ((X)[0]=(Y)[0],  (X)[1]=(Y)[1],  (X)[2]=(Y)[2] )
#define CLEAR(X)  ((X)[0]=0,       (X)[1]=0,       (X)[2]=0      )
#define OR(X,Y)   ((X)[0]|=(Y)[0], (X)[1]|=(Y)[1], (X)[2]|=(Y)[2])
#define EQ(X,Y)   ((X)[0]==(Y)[0]&&(X)[1]==(Y)[1]&&(X)[2]==(Y)[2])
#define ADD(X,Y)  ((Y)>=BIT*2?((X)[2]|=1<<((Y)-BIT*2)): \
                   (Y)>=BIT?((X)[1]|=1<<((Y)-BIT)):((X)[0]|=1<<(Y)))
#define IN(X,Y)   ((Y)>=BIT*2?(X)[2]&(1<<((Y)-BIT*2)): \
                   (Y)>=BIT?(X)[1]&(1<<((Y)-BIT)):  (X)[0]&(1<<(Y)))

#else
/*┌────────────┐
 │関数による集合演算の実装│
 └────────────┘*/
void COPY(set X,set Y) { int i; for (i=0;i<SIZE;i++) X[i]=Y[i];  }
void CLEAR(set X)      { int i; for (i=0;i<SIZE;i++) X[i]=0;     }
void OR(set X,set Y)   { int i; for (i=0;i<SIZE;i++) X[i]|=Y[i]; }

int  EQ(set X,set Y)
{ int i; for (i=0;i<SIZE;i++) if (X[i]!=Y[i]) return 0; return 1; }

void ADD(set X,int Y)
{ int i; for (i=0;Y>=BIT;i++) Y-=BIT; X[i]|=1<<Y; }

int IN(set X,int Y)
{ int i; for (i=0;Y>=BIT;i++) Y-=BIT; return X[i]&(1<<Y); }
#endif

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int id[HEIGHT][HEIGHT];      /* ID の実体                       */
int RevX[NUM],RevY[NUM];     /* 集合要素から(X,Y)座標へ変換する */
int History[NUM];            /* 過去に置いてきたマス            */
int MaxCoin;                 /* 今までで一番多く置けた枚数      */
int LogSize;                 /* 現在の枚数で何通りあるか        */
set Log[500];                /* 現在の枚数での置き方の記録      */
set*Line[NUM-1];             /* 2点を結ぶ直線の集合の早見表    */
set LineBuf[(NUM-1)*NUM/2];  /* Line の実体                     */
set StartPos;                /* 最初に置ける場所の候補          */
set Disused;                 /* 置く必要のない場所              */

/*┌─────┐
 │集合の表示│
 └─────┘*/
void Print(set s)
{
    int x,y,c,i; static char b[HEIGHT][81],col;

    if (s==0&&col) {
        for (i=0;i<HEIGHT;i++) printf("%s\n",b[i]);
        printf("\n"); return;
    }
    for (i=0;i<HEIGHT;i++) {
        y=i-N; sprintf(b[i]+strlen(b[i]),"%*s",abs(y),"");
        for (x=max(y,0)-N;x<=min(y,0)+N;x++)
        { c=ID(x,y); sprintf(b[i]+strlen(b[i]),IN(s,c)?"●":"○"); }
        sprintf(b[i]+strlen(b[i]),"%*s",abs(y)+1,"");
    }
    if (++col==79/(HEIGHT*2+1)) {
        for (i=0;i<HEIGHT;i++) { printf("%s\n",b[i]); b[i][0]=0; }
        printf("\n"); col=0;
    }
}

/*┌─────────────────────────┐
 │集合を右に60度回転する。mirror が 1 なら反転する│
 └─────────────────────────┘*/
void Rotate(set s,int mirror)
{
    set buf; int x,y,t,i;

    CLEAR(buf);
    for (i=0;i<NUM;i++) if (IN(s,i)) {
        x=RevX[i]; y=RevY[i];
        if (mirror) x=-x+y; else { t=x; x=x-y; y=t; }
        t=ID(x,y); ADD(buf,t);
    }
    COPY(s,buf);
}

/*┌───────────────┐
 │MaxCoin 枚以上置けた場合の処理│
 └───────────────┘*/
void Update(int n)
{
    int*p,i,j; set result,old;

    MaxCoin=n;

    /* 回転と鏡像の排除 */
    CLEAR(result);
    for (i=0;i<n;i++) ADD(result,History[i]);
    for (i=0;i<LogSize;i++) for (j=0;j<12;j++) {
        if (j==0) COPY(old,Log[i]); else Rotate(old,j==6);
        if (EQ(old,result)) return;
    }

    /* 配列に結果を記録する */
    if (LogSize>=sizeof Log/sizeof(set))
    { fprintf(stderr,"配列 Log が小さい\n"); exit(1); }
    p=Log[LogSize++]; COPY(p,result);
}

/*┌─────────┐
 │各種テーブルの作成│
 └─────────┘*/
void MakeTable(void)
{
    int i=0,j,dx,dy,k,x,y,z; set*q,u;

    /* ID, RevX, RevY の設定 */
    for (y=-N;y<=N;y++) for (x=-N;x<=N;x++) ID(x,y)=NONE;
    for (y=-N;y<=N;y++) for (x=max(y,0)-N;x<=min(y,0)+N;x++)
    { RevX[i]=x; RevY[i]=y; ID(x,y)=i++; }

    /* 開始点 StartPos の設定 */
    for (y=-N;y<=0;y++) for (x=y;x<=(y-1)/2;x++)
    { j=ID(x,y); ADD(StartPos,j); }

    /* 早見表(上三角行列) のポインタ設定 */
    for (q=LineBuf-1,i=0;i<NUM-1;i++) { Line[i]=q; q+=NUM-i-2; }

    /* 早見表の設定 */
    for (i=0;i<NUM-1;i++) for (j=i+1;j<NUM;j++) {
        dx=RevX[j]-RevX[i]; dy=RevY[j]-RevY[i]; CLEAR(u);
        if (dx==0) dy=1;
        if (dy==0) dx=1;
        for (k=HEIGHT;k>1;k--)
         if (dx&&dx%k==0&&dy&&dy%k==0) { dx/=k; dy/=k; }
        for (k=-HEIGHT;k<=HEIGHT;k++) {
            x=RevX[i]+k*dx; y=RevY[i]+k*dy;
            if (x<-N||x>N||y<-N||y>N) continue;
            if ((z=ID(x,y))!=NONE) ADD(u,z);
        }
        COPY(Line[i][j],u);
     }
}

/*┌────────────────────────────┐
 │再帰呼び出しをしながらマスを埋めてゆく                  │
 │n:置いてきたコインの数. m:最後に置いたコインの位置. s:印│
 └────────────────────────────┘*/
void Sub(int n,int m,set s)
{
    set q; int i,j,k,best=n;

    /* 最良の場合、どれくらいコインを置けるかを数え上げる */
    for (i=m+1;i<NUM;i++) if (!IN(s,i)) best++;
    if (best<MaxCoin) return; /* MaxCoin 以上にならない場合 */

    History[n-1]=m;
    if (n>MaxCoin) LogSize=0;
    if (n>=MaxCoin) Update(n);

    /* 次のループの終了点を k に求める */
    k=2+n-MaxCoin;
    if (k<0) k+=NUM; else k=NUM;

    /* 新たなコインを置いてみる */
    for (i=m+1;i<k;i++) if (!IN(s,i)) {
        COPY(q,s);

        /* 直線上の点に印を付ける */
        for (j=0;j<n;j++) OR(q,Line[History[j]][i]);
        Sub(n+1,i,q); /* 再帰呼び出し */
    }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock(); set s; int i,j;

    MakeTable();
    for (i=0;i<NUM;i++) if (IN(StartPos,i)) {
        Sub(1,i,Disused);

        /* 置く必要のない場所 Disused の設定 */
        CLEAR(s);
        for (j=0;j<12;j++) {
            if (j==0) ADD(s,i); else Rotate(s,j==6);
            OR(Disused,s);
        }
    }
    for (i=0;i<LogSize;i++) Print(Log[i]);
    Print(0); printf("%d枚  %d通り  ", MaxCoin, LogSize);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}