/*
2003/11 十五長方形合流記
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ 以下のような,異なるサイズの長方形が15枚ある。    │
 │  13×60,15×37,16×41,17×51,18×48,       │
 │  19×56,20×44,21×29,23×32,24×31,       │
 │  25×27,26×61,28×40,30×43,42×47        │
 │ これらを1枚ずつすべて使って,隙間なく,重ねることもなく│
 │敷き詰めて正方形を作りたい。全体を回転した解や鏡像の解は別│
 │の解とはしないとして,何通りの敷き詰め方があるだろうか。ま│
 │た,その敷き詰め方を1つ図示してほしい。         │
 └─────────────────────────────┘
 ┌──────┐
 │解答:1通り│
 └──────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │Fig.1 盤の例とその時のリスト構造体            │
 │                             │
 │\0   13   28   44  120            │
 │0┌───┬───┬───┬───            │
 │ │13×60│15×37│16×41│               │
 │37│   ├───┤   │               │
 │41│   │   └───┘               │
 │60└───┘                       │
 │ {4,3,{13,28,44,120 ... },{60,37,41,0 ... }}       │
 │                             │
 │ 盤の状態をどのように表現するかをFig.1に示します。リスト│
 │構造体の最初の整数は、盤を下から見て幾つの区間に分かれてい│
 │るかを表します。次の整数は一番浅い区間の位置を表します。次│
 │の配列は各区間の右の位置を表します。最後の配列は各区間の深│
 │さを表します。リストの実現には単純な配列を使いました。途中│
 │に要素を挿入したり、削除したりするときには後ろのデータがシ│
 │フトします。                       │
 │ プログラムには、再帰呼び出しをしながら長方形を置いてゆく│
 │関数があります。呼び出しの深さが16になったら、長方形が全│
 │て置けたことになるので結果を表示します。そうでなければ、リ│
 │スト構造体から一番浅い区間を探し出します。そして、まだ使用│
 │していない長方形全てについて繰り返すループと、縦横について│
 │繰り返すループに入ります。この2重ループの内側で、選ばれた│
 │長方形を選ばれた方向で、一番浅い区間に置いてみます。長方形│
 │の右や下がはみ出した場合はスキップします。また、回転と鏡像│
 │を排除するため、四隅のうち左上が一番小さい番号の長方形でな│
 │い場合や、左下の番号が右上の番号よりも小さい場合も、スキッ│
 │プします。無事に置くことができたら、のちの表示のために、ど│
 │のような順序と方向で長方形を置いたかを記録します。そして、│
 │その長方形をリスト構造体に挿入し、再帰呼び出しをします。 │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 120×120の配列で処理をしていたときは3分くらい時間がかか│
 │っていました。                      │
 └─────────────────────────────┘
 ┌──────────────┬────┬───────┐
 │コンパイラ         │実行時間│ファイルサイズ│
 ├──────────────┼────┼───────┤
 │Microsoft Visual C++ 6.0  │0.968 秒│ 36864 byte │
 │Microsoft Visual C++ 2003  │0.984 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │1.265 秒│ 54784 byte │
 │gcc-2.953(djgpp)      │1.099 秒│ 110523 byte │
 │gcc-2.953(cygwin)      │1.203 秒│ 20839 byte │
 │LSI C-86 Ver 3.30 試食版  │2.640 秒│ 14340 byte │
 │Turbo C Ver 1.5(small model)│2.690 秒│ 11812 byte │
 ├──────────────┼────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP   │
 └──────────────┴────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define N  15   /* 長方形の数 */
#define W 120   /* 盤の大きさ */

int Rect[N][2]= /* 長方形のサイズ */
{ {13,60},{15,37},{16,41},{17,51},{18,48},
  {19,56},{20,44},{21,29},{23,32},{24,31},
  {25,27},{26,61},{28,40},{30,43},{42,47} };

/*┌────────────────┐
 │配列で実現したリスト構造体の宣言│
 └────────────────┘*/
typedef struct {
    int size;       /* リストの持つ要素の数 */
    int index;      /* 一番浅い場所のリスト番号 */
    int right[N+1]; /* 長方形の右の位置 */
    int top[N+1];   /* 長方形の深さ */
} list[1];

/*┌──────────────────────┐
 │リストpに長方形を挿入したものをリストqとする│
 │qとpを同じリスト構造体にすると上書きする  │
 └──────────────────────┘*/
void InsertList(list q,list p,int right,int bottom)
{
    int i,j,size=p->size,index=p->index,Min;

    if (p->right[index]==right) {
        /* スッポリ収まった場合 */
        for (i=0;i<size;i++)
        { q->right[i]=p->right[i]; q->top[i]=p->top[i]; }
        q->top[index]=bottom; Min=W;
        for (i=0;i<size;i++) if (q->top[i]<Min)
        { Min=q->top[i]; index=i; }
    }else{
        /* 隙間ができる場合 */
        for (i=size;i>index;i--) 
        { q->right[i]=p->right[i-1]; q->top[i]=p->top[i-1]; }
        q->top[index]=bottom; q->right[index]=right; size++;
        for (i=index-1;i>=0;i--)
        { q->right[i]=p->right[i]; q->top[i]=p->top[i]; }
        index++;
    }

    /* 同じ深さが連続した場合リストの要素をマージする */
    for (j=0,i=1;i<size&&q->top[j]!=q->top[i];i++) j++;
    for (;i<size;i++)
     if (q->top[j]==q->top[i]) {
         if (i==index) index=j; else if (i<index) index--;
         q->right[j]=q->right[i];
     } else { j++; q->top[j]=q->top[i]; q->right[j]=q->right[i]; }

    q->size=j+1; q->index=index; /* サイズと index の更新 */
}

/*┌───────┐
 │結果を書き出す│
 └───────┘*/
void Print(int*order,int*dir)
{
    static char map[W][W],buf[16]; static list p;
    int level,n,d,x,y,left,top,right,bottom;

    /* リストの初期化 */
    p->size=1; p->index=0; p->right[0]=W; p->top[0]=0;

    /* 全ての長方形について繰り返す */
    for (level=0;level<N;level++) {

        /* リストから左上の位置を得る */
        if (p->index) left=p->right[p->index-1]; else left=0;
        top=p->top[p->index];

        /* 長方形と方向の履歴から右下の位置を得る */
        n=order[level]; d=dir[level];
        right=Rect[n][d!=0]+left; bottom=Rect[n][d==0]+top;

        /* マップを文字で埋める */
        for (y=top;y<bottom;y++) for (x=left;x<right;x++)
            map[y][x]=(char)(n+'A');

        /* 長方形の大きさの情報をマップに書き込む */
        sprintf(buf," %d×%d ",Rect[n][0],Rect[n][1]);
        memcpy(&map[top+1][left+2],buf,(int)strlen(buf));

        InsertList(p,p,right,bottom); /* リストに長方形を挿入する */
    }

    /* マップを書き出す */
    for (y=0;y<W;y++) {
        for (x=0;x<W;x++) fputc(map[y][x],stdout);
        fputc('\n',stdout);
    }
    fputc('\n',stdout);
}

/*┌─────────────────┐
 │再帰呼び出しをしながらパズルを解く│
 └─────────────────┘*/
void Solve(int level,list p)
{
    static char flag[N];   /* その長方形が使用中かどうかのフラグ */
    static int  order[N];  /* 長方形を置いてきた履歴の番号 */
    static int  dir[N];    /* 長方形を置いてきた方向 */
    static int  top_right; /* 一番右上に置いた長方形の番号 */
    int n,d,right,bottom,top,left,bound; list q;

    if (level==N) { Print(order,dir); return; }

    /* リストから左上の位置と右位置の最大値を得る */
    if (p->index) left=p->right[p->index-1]; else left=0;
    top=p->top[p->index]; bound=p->right[p->index];

    /* 長方形の種類と縦横について繰り返す */
    for (n=0;n<N;n++) if (flag[n]==0) for (d=0;d<2;d++) {

        /* 与えられた長方形と方向から右下の位置を得る */
        right=Rect[n][d!=0]+left; bottom=Rect[n][d==0]+top;

        /* 新しい長方形がはみ出していたらスキップする */
        if (right>bound||bottom>W) continue;

        /* 回転と鏡像ならばスキップする */
        if (right==W&&top==0&&(top_right=n)<order[0]) continue;
        if (bottom==W&&left==0&&n<top_right) continue;
        if (level==N-1&&n<order[0]) continue;

        order[level]=n; dir[level]=d; /* 種類と方向を記録する */
        InsertList(q,p,right,bottom); /* リストに長方形を挿入する */
        flag[n]=1; Solve(level+1,q); flag[n]=0; /* 再帰呼び出し */
    }
}

/*┌────────────────────┐
 │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; static list p={{1,0,{W}}};

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