/**********************************************************************/
/*                                     Ｃmagazine 1995.07 電脳クラブ  */
/*   標    題   カウント・ワン                                        */
/*                                                                    */
/*   解    答   83 個                                                 */
/*                                                                    */
/*   使用機種   FMR-50NL (i486sx 25MHz)                               */
/*   Ｏ    Ｓ   MS-DOS Ver6.2                                         */
/*   コンパイラ LSI C-86 Ver3.30C(試食版)                             */
/*   実行時間   1 秒                                                  */
/*                                                                    */
/**********************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define  HYOJI 0        /* Ｎを全て表示するなら1にする */
#define  KETA  10       /* Ｎは理論上10桁が限界        */

/* グローバル変数 */
int  enu[KETA];         /* Ｎの値   (BCD表現配列)      */
int  one[KETA];         /* Ｎまでの１の個数(BCD表現)   */
int  kosu=0;            /* 条件を満たすＮの個数(解答)  */


/* BCD表現配列の繰り上がり下がり整理 */
int  seiri(int table[])
{
    int  i;

    for (i=0; i<KETA-1; i++) {
        while (table[i]<0) {
            table[i] += 10;
            table[i+1]--;
        }
        while (table[i]>9) {
            table[i] -= 10;
            table[i+1]++;
        }
    }

    /* 10桁を越えていれば真を返す */
    return (table[KETA-1] / 10);
}

/* １の個数＞Ｎ の場合の探索ジャンプ */
int  jump1(void)
{
    int  i;

    /* Ｎ＝(１の個数)とする */
    for (i=0; i<KETA; i++) enu[i]=one[i];

    return 0;
}

/* １の個数==Ｎ の場合の処理 */
int  mikke(void)
{
    /* 解答個数＋＋ */
    kosu++;

    /* Ｎと解答個数を表示 (HYOJI=1 とすると) */
    #if HYOJI
    {
        int  i;

        for (i=KETA-1; i>=0; i--)
            printf("%d",enu[i]);
        printf(" (%d個目)\n",kosu);
    }
    #endif

    /* 次の探索のためにＮ＋＋ */
    enu[0]++;

    /* enu を整理し10桁を越えたら真を返す */
    return (seiri(enu));
}

/* １の個数＜Ｎ の場合の探索ジャンプ */
int  jump2(void)
{
    int  i, status=0, sa[KETA];

    /* Ｎと(１の個数)の差を求める */
    for (i=0; i<KETA; i++)
        sa[i] = enu[i]-one[i];
    seiri(sa);

    /* 差の1/10を加算する */
    for (i=1; i<KETA; i++) {
        if (sa[i]) {
            enu[i-1] += sa[i];
            status=1;
        }
    }

    /* 差が１桁で enu に変化が無かった場合はＮ＋＋ */
    if (!status) enu[0]++;

    /* enu を整理し10桁を越えたら真を返す */
    return (seiri(enu));
}

/* Ｎまでの１の個数をダイレクトに計算する */
int  count_one(void)
{
    int i, j;

    /* １の個数を入れる配列 one を初期化 */
    for (i=0; i<KETA; i++) one[i]=0;

    /* １の個数を計算する */
    for (i=0; i<KETA; i++) {
        for (j=1; j<=i; j++)
            one[i-1] += enu[i];
        if (enu[i] == 1) {
            for (j=0; j<i; j++)
                one[j] += enu[j];
            one[0]++;
        } else {
            if (enu[i] > 1) one[i]++;
        }
    }

    /* 10桁を越えた場合大小比較返り値以外を返す */
    if (seiri(one)) return 2;

    /* one と enu を大小比較し結果を返す */
    for (i=KETA-1; i>=0; i--) {
        if (one[i] > enu[i]) return  1;
        if (one[i] < enu[i]) return -1;
    }
    return 0;
}

/* メイン処理 */
void  main(void)
{
    int  i, end_flag=0;

    /* Ｎ＝１(初期化) */
    enu[0]=1;
    for (i=1; i<KETA; i++) enu[i]=0;

    /* 探索処理 */
    while (!end_flag) {

        /* Ｎまでの１の個数を計算し結果に応じた処理をする */
        switch (count_one()) {
            case  1 : end_flag=jump1(); break;  /* １の個数＞Ｎ */
            case  0 : end_flag=mikke(); break;  /* １の個数==Ｎ */
            case -1 : end_flag=jump2(); break;  /* １の個数＜Ｎ */
            default : end_flag=1;               /* 10桁オーバー */
        }
    }
    printf("解答 %d 個",kosu);
}

/*************************** ( プログラムの説明､感想 ) ****************

・プログラムの説明

    何桁の数であれ全桁がオール９のＮはその付近での１の含有比率が最も少
  ない数となります。さて、１０桁オール９のＮを考えた場合、１０の１０乗
  個の１があり、それは１１桁の数なので、もはやそれ以上のＮで条件を満た
  すＮは無く、Ｎの上限値は１０桁であると言えます。そこでＮと１の個数を
  要素数１０のＢＣＤ表現配列として処理しました。
    さて次に、無駄な探索をジャンプする考え方として、
   (1) １の個数 ＞ Ｎ ならば、最大限譲歩して以後１が全く出現しなかった
    と想定すると「Ｎ＝１の個数」まで直接ジャンプしてもかまわない。
   (2) １の個数 ＜ Ｎ ならば、最大限譲歩して以後１０桁全てが１だったと
    想定すると「その差の 1/10 を加算」までジャンプしてもかまわない。
  となりますが、このジャンプを行う為にはＮから１の個数をダイレクトに計
  算するルーチンを作らねばなりません。

・感  想

    Ｃ言語を始めて４ケ月目になります。Ｃマガジンの４月号の付録のLSIC86
  と電脳クラブの２つがきっかけですっかりＣ言語にはまってしまいました。
  今まではＢＡＳＩＣやＣＯＢＯＬ専門だったのですが、Ｃ言語の高速性に驚
  きながら、電脳クラブを最良の学習教材として勉強中です。

***********************************************************************/