/*
2002/10 割り算の得意な金庫
coded by Isaku WADA
 ┌───────────────────────────┐
 │ Fig.2のように,0〜9の数字が書かれたダイヤルが5つ│
 │ついた金庫がある。この金庫,開け方がちょっと変わってい│
 │る([前提],[操作手順])。Fig.2の状態からたとえば03316 │
 │→02316→12316→12315と動かすと,順に2,3,4,5で割り│
 │切れている。しかし,次の6で割り切れる数を12315から作 │
 │れないので,この場合はここでおしまい。さて,金庫のセキ│
 │ュリティ上,できるだけ大きなNを設定したい。ちゃんと金│
 │庫を開けることができる,最大のNはいくつだろうか。  │
 │[前提]                        │
 │ @左のダイヤルから万の位/千の位/百の位/十の位/一の位│
 │  の数字を表しており,この5桁の数を「D数」と呼ぶ。│
 │  Fig.2のD数は「03316」              │
 │ A除数nを考え,n=2としてスタート        │
 │[操作手順]                      │
 │ @まず最初に,D数に偶数をセットする。当然,この数は│
 │  n(=2)で割り切れる                │
 │ A除数nに1を足す                 │
 │ Bどれか1つのダイヤルを選び,右か左に1だけ回す  │
 │ CBでセットされたD数が,nで割り切れればDへ。割り│
 │  切れなければ金庫は空かずに終了          │
 │ Dnがあらかじめ金庫に設定されている数Nと同じ場合,│
 │  金庫が開く。n<NならAへ            │
 │                           │
 │ Fig.2 割り算の得意な金庫             │
 │                           │
 │   万    千    百    十    一   │
 │   ↓    ↓    ↓    ↓    ↓   │
 │  901  234  234  012  567  │
 │  8  2 1  5 1  5 9  3 4  8  │
 │  7  3 0  6 0  6 8  4 3  9  │
 │  654  987  987  765  210  │
 │                           │
 └───────────────────────────┘
 ┌───────────────────────────┐
 │解答:N=32                    │
 │45320 55320 65320 75320 85320 75320 76320 76329 76320 │
 │76329 76320 76310 76300 76200 77200 78200 78210 68210 │
 │68200 67200 68200 78200 79200 69200 69290 69390 69300 │
 │69310 69210 59210 59200                │
 ├───────────────────────────┤
 │(K=1:N=10) (K=2:N=10) (K=3:N=10) (K=4:N=21) (K=5:N=32)│
 │(K=6:N=35) (K=7:N=43) (K=8:N=51) (K=9:N=61)      │
 └───────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.01470 秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.01378 秒│ 35328 byte │
 │Borland C++ 5.5 for Win32  │0.01600 秒│ 53760 byte │
 │gcc-2.953(djgpp)      │0.01258 秒│ 109133 byte │
 │gcc-2.953(cygwin)      │0.01178 秒│ 19844 byte │
 │LSI C-86 Ver 3.30 試食版  │0.04780 秒│ 13772 byte │
 │Turbo C Ver 1.5(small model)│0.06650 秒│ 11248 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │問題の性質から、解の探索をするときに、除数nを2から始めてN│
 │まで増やしていっても、除数nをNから始めて2まで減らしていっ│
 │ても、共に金庫を開ける手順を求めることができます。後者の場合│
 │、ダイヤルの回し方を示すときに、探索で得られた手順を逆順に表│
 │示する必要があります。                   │
 │                              │
 │nを2から始める場合、nが小さいときに割り切れるD数が多いた│
 │めに、計算量が多くなります。一方、nをNから始める場合、nが│
 │大きいときには、割り切れるD数が少ないために、計算量が少なく│
 │なります。この計算量の差は非常に大きいので、今回は後者の方法│
 │で探索しました。                      │
 │                              │
 │自明な解として 20000,30000, ... ,90000,00000 があるので、最 │
 │大のNは10以上であることがわかります。          │
 │                              │
 │よって、プログラムは、まず、Nを10にして探索を行います。そ│
 │して、解が見つかる度に、経過を記録した後、Nをインクリメント│
 │して、探索をやり直します。このようにして、Nを増やしてゆき、│
 │探索が終了しても解が見つからない場合、N−1が最大のNだった│
 │ことがわかり、プログラムは記録を表示して終了します。    │
 │                              │
 │他に、高速化の工夫として、n=Nのとき、D数をNの倍数に限っ│
 │て探索を始めています。また、D数からダイヤルを設定するために│
 │、sprintf() を使わずに、割り算や余りを使わない関数     │
 │SetDialByD()を自分で書きました。さらに、ダイヤルからD数を求│
 │める代わりに、ダイヤルを回すと同時にD数を増減させています。│
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │探索の順序を逆にするだけで、計算時間が約1万分の1になりまし│
 │た。興味があったので、Nを32に設定したときに、何通りの金庫│
 │の開け方があるかどうかを調べたところ、6308通りもありまし│
 │た。                            │
 └──────────────────────────────┘
*/

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

/*┌────────┐
 │定数・変数の宣言│
 └────────┘*/
#define K  5      /* 桁数(ダイヤルの個数)1〜9 */
#define M 61      /* Nの予想最大値以上の数 */
int  N;           /* あらかじめ金庫に設定されている数N */
int  n;           /* 除数n */
int  Flag;        /* 現在のNで解が見つかれば1 */
int  Dial[K];     /* 各ダイヤルの現在の数字 */
long D;           /* D数 */
long MaxD;        /* 例えば K==5 なら 99999 */
long Base1[K];    /* 例えば K==5 なら 10000,1000,100,10,1 */
long Base9[K];    /* 例えば K==5 なら 90000,9000,900,90,9 */
long Log[M+2];    /* 一連のD数を記録する */
long Result[M+2]; /* 解が見つかったときの Log[] を記録する */

/*┌────┐
 │解の表示│
 └────┘*/
void Print(void)
{
    int i;

    printf("K=%d  N=%d\n",K,N);
    for (i=2;i<=N;i++) printf(" %0*ld",K,Result[i]);
    printf("\n");
}

/*┌────────────────────────┐
 │D数を十進の各桁に分解し、配列 Dial[] を設定する│
 └────────────────────────┘*/
void SetDialByD(long D)
{
    int i,c; long base;

    for (i=0;i<K;i++) {
        base=Base1[i];
        for (c=0;D>=base;c++) D-=base;
        Dial[i]=c;
    }
}

/*┌───────────────────────────┐
 │pos 位置のダイヤルを dir==0 なら右回りに、dir==1 なら │
 │左回りに一つだけ回す。同時にD数も増減させる     │
 └───────────────────────────┘*/
void Turn(int pos,int dir)
{
    if (dir) if (Dial[pos]==9) { Dial[pos]=0; D-=Base9[pos]; }
             else              { Dial[pos]++; D+=Base1[pos]; }
    else     if (Dial[pos]==0) { Dial[pos]=9; D+=Base9[pos]; }
             else              { Dial[pos]--; D-=Base1[pos]; }
}

/*┌──────────────────────────┐
 │n=N から始めて、n==2 になったら記録をする。     │
 │そうでなければ、順にダイヤルを回して、余りを計算し、│
 │条件を満たしていれば、自分自身を呼び出す      │
 └──────────────────────────┘*/
void Try(void)
{
    int p,d;

    if (n==2) {
        for (p=2;p<=N;p++) Result[p]=Log[p];
        Flag=1; return;
    }
    for (p=0;p<K;p++) for (d=0;d<2;d++) {
        Turn(p,d); n--;   /* 回してみる */
        if (D%n==0) { Log[n]=D; Try(); } /* 再帰呼び出し */
        n++; Turn(p,!d);  /* 元に戻す */
        if (Flag) return; /* 解が見つかっているので処理を中止する */
    }
}

/*┌────────┐
 │パズルを1回解く│
 └────────┘*/
void Solve(void)
{
    int i;

    /* Base1[], Base9[], MaxD を求める */
    Base1[K-1]=1; Base9[K-1]=9;
    for (i=K-2;i>=0;i--)
    { Base1[i]=Base1[i+1]*10; Base9[i]=Base9[i+1]*10; }
    MaxD=Base1[0]*10-1;

    N=9; Flag=1; /* N=10 までなら自明な解がある */
    do {
        if (Flag) /* 解が見つかったのでNを増やしてみる */
        { N++; n=N; D=0; Flag=0; }
        SetDialByD(D); Log[n]=D; Try(); D+=N;
    } while (D<=MaxD||Flag); /* 解がないまま最大値を超えたら終了 */
    N--;
}

/*┌────────────────────┐
 │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(); long i,num;

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