/* 笑わない数学者/Mathematical Goodbye      */
/* 森　博嗣 講談社文庫                      */
/*  p.74-75                                 */
/* 「さて，では，もう一つ問題を出そう．五つのビリヤードの玉を，真珠のネックレスのように，                       */
/*  　リングにつなげてみるとしよう．玉には，それぞれナンバが書かれている．さて，この五つの玉のうち，            */
/*　　幾つ取っても良いが，隣どうし連続したものしか取れないとしよう．一つでも，二つでも，五つ全部でも良い．      */
/*　　しかし，離れているものは取れない．この条件で取った玉のナンバを足し合わせて，１から２１までの              */
/*　　すべての数ができるようにしたい．さあ，どのナンバの玉をどのように並べて，ネックレスを作れば良いかな？」    */

/* 2004/08/28(Sat)  T.Shirai    */

/* （拘束条件の不足）：同じナンバの玉が複数存在しても良いのか？             */
/* （拘束条件の不足）：玉の最大の番号はいくつか？（常識的に考えて２１以下） */

/* （分かっていること）：１と２のボールは必要である．                       */
/* （分かりきっていること）：ナンバ０以下のボールは存在しない               */
/* （分かっているのにトボけること）：５つのボールの合計は２１よりも大きいかも知れない   */
/* （ちなみに答えの一つは）：1-3-10-2-5         */

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

#define SUM_MAX         21          /* １からSUM_MAXまでの数を作る  */
#define BALL_NUM        5           /* BALL_NUM個のボール，サイズBALL_NUMのQueueバッファ，BALL_NUMを法とする    */
#define MAX_BALL_NUM    SUM_MAX     /* 玉の最大のナンバはMAX_BALL_NUM       */

struct bbT {
    char    num[BALL_NUM];
    int     c1, c2, c3, c4, c5, c6;     /* 確認用   */
} bb;


/* 新しい玉の組み合わせを作成する   */
/* 戻り値： すべての組み合わせが終了 = 0    */
/*          新しい組み合わせを作成   = 1    */
int countup_ball(void)
{
    int i, j;
    int flag  = 0;
    bb.c1++;
    for (i = 0; i < BALL_NUM; i++) {
        if (++bb.num[i] > MAX_BALL_NUM) {
            /* 現在着目している玉が最大値を超えたら１に戻し，次の桁に移る   */
            bb.num[i] = 1;
            continue;
        } else {
            flag = 1;
            break;
        }
    }
    return (flag);
}

void printout_balls(void)
{
    int i;
    for (i = 0; i < BALL_NUM; i++) printf("[%d] ", bb.num[i]);
    puts("");
}

/* 与えられた数になる玉の組み合わせが存在するか？       */
/* 引数：合計の数                                       */
/* 戻り値：合計の数と等しくなる組み合わせが存在する=1   */
/* 　　　　合計の数と等しくなる組み合わせが存在しない=0 */
int exist_combination(int total)
{
    int     i, j, k;
    int     sum;

    for (i = 0; i < BALL_NUM; i++) {        /* 基準とする玉の位置   */
        for (j = 1; j <= BALL_NUM; j++) {   /* 足し合わせる玉の数   */
            sum = 0;
            for (k = i; k < i + j; k++) sum += bb.num[k % BALL_NUM];
            if (sum == total) return 1;
        }
    }
    return 0;
}

void check_ball(void)
{
    int i, j, k;
    int s;
    /* エラーチェック   */
    for (i = 0; i < BALL_NUM; i++) {
        if (bb.num[i] < 0 || bb.num[i] > MAX_BALL_NUM) {
            printout_balls();
            printf("Abnormal Ball Number\n");
            exit(2);
        }
    }
    bb.c2++;
#if 1
    /* 同じナンバのボールを許さないならば   */
    for (i = 0; i < BALL_NUM - 1; i++) {
        for (j = i + 1; j < BALL_NUM; j++) {
            if (bb.num[i] == bb.num[j]) return;
        }
    }
#endif
    bb.c3++;
    /* 全ての玉のナンバを足しても最大値に達しない   */
    for (i = s = 0; i < BALL_NUM; i++) s += bb.num[i];
    if (s < SUM_MAX) return;
    bb.c4++;
    /* 1 と 2を含まないならば   */
    for (i = j = 0; i < BALL_NUM; i++) {
        if (bb.num[i] == 1) j |= 1;
        if (bb.num[i] == 2) j |= 2; 
    }
    if (j != 3) return;
    bb.c5++;
    /* １からSUM_MAXの組み合わせを選択できるか？    */
    for (s = 1; s <= SUM_MAX; s++) {
        if (exist_combination(s) != 1) return;
    }
    printout_balls();
    bb.c6++;
}

int main(void)
{
    int i;
    
    /* 初期処理 */
    for (i = 0; i < BALL_NUM; i++) bb.num[i] = 1;
    bb.num[0] = 0;
    bb.c1 = bb.c2 = bb.c3 = bb.c4 = bb.c5 = bb.c6 = 0;
    /* ボールの考えられすべての組み合わせを作り，   */
    /* それが条件を満たすかチェックする             */
    while (countup_ball())  {
        check_ball();
    }
    fprintf(stderr, "全ての玉の組み合わせ（重複含む）は%dパターン\n", bb.c2);
    fprintf(stderr, "そのうち%.1lf[％] (%d個)は玉のナンバが重複している．\n", (double)(bb.c2 - bb.c3) / bb.c2 * 100.0, bb.c2 - bb.c3);
    fprintf(stderr, "残り%d個のうち%.1lf[％](%d個)は全ての玉のナンバを足しても%dに満たない．\n", bb.c3, (double)(bb.c3 - bb.c4) / bb.c3 * 100.0, bb.c3 - bb.c4, SUM_MAX);
    fprintf(stderr, "残り%d個のうち%.1lf[％](%d個)は１と２を含まない．\n", bb.c4, (double)(bb.c4 - bb.c5) / bb.c4 * 100.0, bb.c4 - bb.c5);
    fprintf(stderr, "残り%d個のうち%.4lf[％](%d個)は１から%dの組み合わせを実現できない．\n", bb.c5, (double)(bb.c5 - bb.c6) / bb.c5 * 100.0, bb.c5 - bb.c6, SUM_MAX);
    fprintf(stderr, "最終的に，全ての玉の組み合わせ%d個のうち，条件を満たす組み合わせは%.4lf[％]である．\n", bb.c2, (double)bb.c6 / bb.c2 * 100.0);
    return (1);
}