/*
2000/06 循環する数列
coded by Isaku WADA
 ┌──────────────────────────────┐
 │次のような漸化式で表される数列がある。           │
 │  an+1=f(an)-an                      │
 │ ここで,f(x)は,xを構成する数字を降順に(大きな数字から順 │
 │に)並べ替える関数である。つまり「整数anを降順に並べ替えたも │
 │のからanを引いたものをan+1とする」ということだ(各項は0以上の │
 │整数であることとする)。たとえば,a0=547とすると,      │
 │a1=754-547=207,a2=720-207=513…となる。この例の場合,a5で0 │
 │になってしまうが,次の例のように,循環する場合もある。   │
 │  3996,5967,3798,6075,1575,5976,3789,6084,2556  │
 │この2556の次は3996に戻る。この循環は9個の相異なる数で構成さ │
 │れているが,では,これよりも長い,つまり10個以上の数で構成 │
 │される循環をひとつお答えいただきたい。           │
 └──────────────────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │桁数を固定したプログラムを作成しました。         │
 │高速化のために以下の工夫をしました。           │
 │                             │
 │●数列が循環しているかどうかを判定するのにハッシングを  │
 │使って高速化しました。                  │
 │                             │
 │●数字が過去に出現したかどうかを巨大なビット配列に記録する│
 │ようにしました。この方法は高速ですが、メモリをたくさん消費│
 │するので USE_BIT_ARRAY マクロが 1 以外の場合は、この方法を│
 │行わないようにしました。                 │
 │                             │
 │●たいていの計算機は割り算と余りは、足し算の数十倍時間が │
 │かかります。ですから、割り算と余りは使いませんでした。  │
 │また、掛け算も87行目でしか使いませんでした。      │
 │                             │
 │●桁配列から整数値への変換する関数は使いますが、整数値から│
 │桁配列へ展開する関数は、用意はしましたが使いませんでした。│
 │                             │
 │●数列の桁数が増えることはないので、次の項に進んだときに、│
 │桁数が減ったら探索を止めます。また、プログラムの他の部分 │
 │では、桁数は不変という前提で高速化しました。       │
 └─────────────────────────────┘
 ┌────────────────────────────┐
 │・感想                         │
 │                            │
 │「数列の性質をよく見極めて…」とのことですが、それらしい│
 │性質を発見することができませんでした。それが残念です。 │
 └────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define KETA  8 /* 桁数:最大で19 */
#define LEN  10 /* 周期 */

/* clock() をサポートしない MS-DOS コンパイラ用の clock()
LSI C-86 試食版でも 1/1000 秒単位の経過時間を返すようになる
Visual C++、Borland C++ Builder、UNIX 等では自動的に無視される */
#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) 
{
    static int day[12]={0,31,59,90,120,151,181,212,243,273,304,334};
    union REGS t,d; long Time,Date; static long Date0,Time0;
    t.h.ah=0x2c; d.h.ah=0x2a; intdos(&t,&t); intdos(&d,&d);
    Time=t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
    Date=d.x.cx*365L+d.x.cx/4+day[d.h.dh-1]+d.h.dl;
    if ((d.x.cx%4)==0&&d.h.dh<=2) Date--;     /* うるう年の調整 */
    if (Date0==0) { Date0=Date; Time0=Time; } /* 最初は0を返す */
    if (Date-Date0>=24) return-1; /* 24日以上経過すると-1を返す */
    return(Date-Date0)*86400000L+Time-Time0;
}
#endif

/*┌────────────────────────────┐
 │__int64 の代わりに long long や Long を使う処理系もある │
 └────────────────────────────┘*/
#if KETA <= 9
#define LONG long
#else
#ifdef __GNUC__
#define LONG unsigned long long
#else
#define LONG unsigned __int64
#endif
#endif

#define HASH_SIZE 4096 /* ハッシュテーブルの大きさ(2の累乗) */
#define HASH_FUNCTION(X) ((int)((X)&(HASH_SIZE-1)))
#define MUL10(X) (((X)<<3)+((X)<<1)) /* 10 倍した値 */

/*┌────────────────────────┐
 │循環しているかどうかを判定するためのリストの要素│
 └────────────────────────┘*/
typedef struct node_t {
    LONG value; /* 要素の値 */
    int next;   /* ハッシュリストでの次の要素 */
} node_t;

LONG Min=1; /* 例えば KETA が 4 ならば 1000 のように起点を表す */
LONG Max=5; /* 例えば KETA が 4 ならば 5000 のように終点を表す */
LONG TenPowerTable[KETA]={1}; /* 1,10,100,1000 ... */
double StartTime;             /* clock() の最初の値 */
node_t DataTable[HASH_SIZE];  /* 循環を格納する */
int    HashTable[HASH_SIZE];  /* ハッシュテーブル */
int    NumOfValue;            /* 循環の長さ */

/*┌───────┐
 │f(x)-x を返す │
 └───────┘*/
LONG next(LONG x)
{
    char counter[10]; int i,j,c; LONG v,t=x;

    /* 数字の出現度数を求める */
    for (i=0;i<10;i++) counter[i]=0;
    for (i=KETA-1;i>=1;i--) {
        v=TenPowerTable[i];
        for (c=0;t>=v;c++) t-=v;
        counter[c]++;
    }

    /* 最後の桁が0の場合0を返して強制的に打ち切らせる */
    if (t==0) return 0;
    counter[(int)t]++;

    /* 数字を降順に並べた場合の値を再構成する */
    for (t=0,i=9;i>=0;i--) for (j=counter[i];j>0;j--) t=MUL10(t)+i;

    return t-x;
}

/*┌───────────────┐
 │高速に長整数を文字列に変換する│
 └───────────────┘*/
char*Long2Str(LONG t)
{
    static char buf[KETA+1]; LONG v; int i,c; char*p=buf;

    for (i=KETA-1;i>=0;i--) {
        v=TenPowerTable[i];
        for (c='0';t>=v;c++) t-=v;
        *p++=(char)c;
        if (i!=0&&(i%3)==0) *p++=',';
    }
    *p=0;
    return buf;
}

/*┌───────────┐
 │経過時間を文字列にする│
 └───────────┘*/
char*TimeStr(void)
{
    static char buf[32]; int hour,minute; double Time;

    Time=(clock()-StartTime)/CLOCKS_PER_SEC;
    hour=(int)(Time/3600.0);
    Time-=hour*3600.0;
    minute=(int)(Time/60.0);
    Time-=minute*60.0;
    sprintf(buf,"%02d:%02d:%06.3f",hour,minute,Time);
    return buf;
}

/*┌────────┐
 │結果を画面に書く│
 └────────┘*/
void PrintResult(int i,LONG start)
{
    printf("%s 桁数=%2d 周期=%2d 実行時間=%s\n",
        Long2Str(start),KETA,NumOfValue-i,TimeStr());
    for (;i<NumOfValue;i++)
        printf("%s\n",Long2Str(DataTable[i].value));
    printf("\n");
    exit(0);
}

/*┌─────────────────┐
 │出発点 start から1系列だけ調べる │
 └─────────────────┘*/
void SequenceLoop(LONG start)
{
    LONG a; int i,hash;

    for (a=start;a>=start;a=next(a)) {
        hash=HASH_FUNCTION(a);
        for (i=HashTable[hash];i;i=DataTable[i].next)
         if (DataTable[i].value==a) {
             if (NumOfValue-i>=LEN) PrintResult(i,start);
             return;
         }
        DataTable[NumOfValue].value=a;
        DataTable[NumOfValue].next=HashTable[hash];
        HashTable[hash]=NumOfValue;
        NumOfValue++;
    }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    LONG start; int i; long k=0;

    StartTime=clock();
    for (i=1;i<KETA;i++) {
        TenPowerTable[i]=MUL10(TenPowerTable[i-1]);
        Min=MUL10(Min);
        Max=MUL10(Max);
    }
    for (start=Min+8;start<Max;start+=9) {
        if ((k++&((1L<<15)-1))==0) {
            fprintf(stderr,"%s %s\r",Long2Str(start),TimeStr());
            fflush(stderr);
        }
        NumOfValue=1;
        SequenceLoop(start);
        for (i=1;i<NumOfValue;i++)
            HashTable[HASH_FUNCTION(DataTable[i].value)]=0;
    }
    printf("循環は見つかりませんでした. 実行時間:%s\n",TimeStr());
    return 0;
}