//*************************************************************************
// 簡易ロト問題を解く(最適解を調べる)     by takaken 2005/02
//*************************************************************************
#include <stdio.h>
#include <time.h>

#if 1
    // ５個から３個以上
    #define  R  5
    #define  H  3
    #define  MH(n) (5*(n)*(n) - 50*(n) + 126)
#else
    // ３個から２個以上
    #define  R  3
    #define  H  2
    #define  MH(n) (3*(n) - 8)
#endif

#define  BOOL int
#define  TRUE  1
#define  FALSE 0

#define  MAX_TABLE 5000
#define  MAX_DEPTH  100
#define  MAX_N       16

int  N, NCR, DEPTH, MAX_HIT;
int  PTN[MAX_TABLE], HIT[MAX_TABLE];
int  SEL[MAX_DEPTH];

int  ANS_IDX;
int  ANS_TBL[MAX_DEPTH];

//*************************************************************************
// サブルーチン
//*************************************************************************
// 全パターン(nCr)を生成する
BOOL Combination(int r, int i, int bits)
{
    if (r == R) {
        if (NCR == MAX_TABLE) return FALSE;
        PTN[NCR++] = bits;
    } else {
        for ( ; i<N; i++)
            if (!Combination(r+1, i+1, bits | (1 << i))) return FALSE;
    }
    return TRUE;
}
// ビットパターンを表示する
void DispBits(int bits)
{
    int  i, bit;

    for (i=0, bit=1<<(N-1); i<N; i++, bit>>=1)
        printf("%d", (bits & bit)? 1: 0);
}
// ヒット判定関数
BOOL IsHit(int bits)
{
    if (!bits) return FALSE;    // 0

    bits &= (bits - 1);
    if (!bits) return FALSE;    // 1
#if H == 2
    return TRUE;    // 2以上
#endif
    bits &= (bits - 1);
    if (!bits) return FALSE;    // 2

    return TRUE;    // 3以上
}
// ヒットテーブルを戻す
void HitOff(int bits)
{
    int  i;

    for (i=0; i<NCR; i++)
        if (IsHit(PTN[i] & bits)) HIT[i]--;
}
// ヒットテーブルを更新する
BOOL HitOn(int bits, int *nohit)
{
    int  i, retc = FALSE;

    *nohit = 0;
    for (i=0; i<NCR; i++) {
        if (IsHit(PTN[i] & bits)) {
            if (!HIT[i]) retc = TRUE;   // 貢献しいてる
            HIT[i]++;
        } else {
            if (!HIT[i]) (*nohit)++;    // ヒットしていない数
        }
    }
    return retc;
}
// 連続性テーブルをbitsで更新する
int *Group(int group2[], int group1[], int bits)
{
    int  i, bit, cnt=1;

    for (i=N-1,bit=3<<(N-2); i; i--,bit>>=1) {
        // 次の位置(下位)と連続しているなら
        if (group1[i]==0 && group1[i-1]!=1 && ((bits & bit)==bit || (bits & bit)==0)) {
            group2[i] = 0;  // 連続中の印
            cnt++;          // 連続数カウントアップ
        } else {
            group2[i] = cnt;// 連続数を書き込む
            cnt = 1;        // 連続数の初期化
        }
    }
    group2[i] = cnt;

    return group2;
}
// 対称性を考慮したユニークパターンか？(右寄せをユニークとする)
BOOL IsUnique(int group[], int bits)
{
    int  i, bit, flag;

    for (i=0,bit=1; i<N; i++,bit<<=1) {
        if (group[i]) flag = FALSE;     // 連続性が途切れた
        if (group[i] != 1) {
            if (bits & bit) {
                if (flag) return FALSE; // 既に0が出現しているならユニークでない
            } else {
                flag = TRUE;            // 0が出現した
            }
        }
    }
    return TRUE;
}
//*************************************************************************
// 総当り法(再帰関数)
//*************************************************************************
BOOL Backtrack(int n, int i, int group1[], int nohit)
{
    int  bits, group2[MAX_N];

    if (nohit == 0) return TRUE;    // 解を発見した

    // (枝刈り１) 下限値を使って解に達しないと判断した場合は戻る
    if ((DEPTH - n) * MAX_HIT < nohit) return FALSE;

    for ( ; i<NCR; i++) {
        bits = PTN[i];
        // (枝刈り２) 対称性を考慮して等価パターンは排除する(←効果大)
        if (IsUnique(group1, bits)) {
            // (枝刈り３) 新たなヒットに貢献しないものは無視してよい
            if (HitOn(bits, &nohit)) {  // ヒット処理
                SEL[n] = bits;          // 選択パターンを保存
                if (Backtrack(n+1, i+1, Group(group2, group1, bits), nohit))
                    return TRUE;
            }
            HitOff(bits);               // ヒット処理を戻す
        }
    }
    return FALSE;
}
//*************************************************************************
// 欲張り法
//*************************************************************************
BOOL HigherBound(void)
{
    int  i, j, bits, temp, hit, maxhit, nohit;
    int  a, b, update;

    // 最大ヒット数のパターンを選択していく
    do {
        // 最大ヒット数のパターン(bits)を求める
        for (maxhit=i=0; i<NCR; i++) {
            temp = PTN[i];
            for (hit=j=0; j<NCR; j++)
                if (!HIT[j] && IsHit(PTN[j] & temp)) hit++;
            if (hit > maxhit) {
                maxhit = hit;
                bits = temp;
            }
        }
        // 最大ヒット数のパターン(bits)を選択する
        if (ANS_IDX == MAX_DEPTH) return FALSE;
        ANS_TBL[ANS_IDX++] = bits;
        HitOn(bits, &nohit);
    } while (nohit);

    // ２個を１個で代用できるか
    do {
        update = FALSE;
        for (a=0; a<ANS_IDX-1; a++) {
            HitOff(ANS_TBL[a]); // 一旦削除
            for (b=a+1; b<ANS_IDX; b++) {
                HitOff(ANS_TBL[b]); // 一旦削除
                // １つ追加して総てヒット可能か
                for (j=NCR-1; j>=0; j--) {
                    bits = PTN[j];
                    HitOn(bits, &nohit);
                    if (nohit == 0) break;
                    HitOff(bits);
                }
                // 成功したので結果を更新する
                if (j >= 0) {
                    ANS_TBL[a] = bits;
                    for (j=b+1; j<ANS_IDX; j++)
                        ANS_TBL[j-1] = ANS_TBL[j];
                    ANS_IDX--;
                    update =TRUE;
                    break;
                }
                HitOn(ANS_TBL[b], &nohit);  // 一旦削除ものを戻す
            }
            if (update) break;
            HitOn(ANS_TBL[a], &nohit);  // 一旦削除ものを戻す
        }
    } while (update);

    return TRUE;
}
//*************************************************************************
// エントリーポイント
//*************************************************************************
int main(void)
{
    int  i, group[MAX_N];
    clock_t stime;

    for (N=R; N<=MAX_N; N++) {
        // 初期化(全パターンを求める)
        stime = clock();
        NCR = ANS_IDX = 0;
        if (!Combination(0, 0, 0)) break;   // MAX_TABLE 不足
        printf("%d->%d: N=%d,", R, H, N);

        // 欲張り法(上限値を求める)
        for (i=0; i<NCR; i++) HIT[i] = 0;
        if (!HigherBound()) break;          // MAX_DEPTH 不足
        printf(" (max=%d)", ANS_IDX);

        // 総当り法(上限値未満を順次調べて最適解を得る)
        for (i=1; i<N; i++) group[i] = 0;
        group[0] = N;
        MAX_HIT = MH(N);
        for (DEPTH=ANS_IDX-1; ; DEPTH--) {
            for (i=0; i<NCR; i++) HIT[i] = 0;
            printf(">");
            if (!Backtrack(0, 0, group, NCR)) break;
            // 解の記録を更新する
            ANS_IDX = DEPTH;
            for (i=0; i<DEPTH; i++) ANS_TBL[i] = SEL[i];
        }

        // 結果の表示
        printf(", min=%d", ANS_IDX);
        printf(" (time=%.2fsec)\n", ((float)(clock() - stime)) / CLOCKS_PER_SEC);
        for (i=0; i<ANS_IDX; i++) {
            DispBits(ANS_TBL[i]);
            printf("\n");
        }
    }
    return 0;
}