/*
2003/02 逆さ電卓数字
coded by Isaku WADA
 ┌────────────────────────────┐
 │ デジタル時計や電卓に昔からよく使われている数字(ここで│
 │は電卓数字と呼ぶ)の表記では,逆さから見ても数字として読│
 │めるものがある。つまり,0,1,2,5,6,8,9は,逆│
 │さから見ると0,1,2,5,9,8,6と読めるのだ。  │
 │ さて,Fig.3の四角に逆さから読める電卓数字を1字ずつ入│
 │れて式を成り立たせ,さらに全体を180度回転して逆さから│
 │見ても数式として成立するようにしたい。Fig.3にその例を示│
 │す。このような式は例も入れて何通り作れるだろうか?ただし│
 │,逆さにした場合も含めて各3桁の数の左端には0はこないこ│
 │ととし,また,和をとっている2数を入れ替えたものは別の解│
 │とはしない。                      │
 │                            │
 │ Fig.3 逆さから見ても成立する式           │
 │                            │
 │    □□□+□□□=□□□−□□□         │
 │    192+582=992−218         │
 │                            │
 └────────────────────────────┘
 ┌────────────────────────────┐
 │解答:195 (1桁:1)(2桁:10)(3桁:195)(4桁:4650)(5桁:118843)│
 └────────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.02109 秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.01453 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.01188 秒│ 53760 byte │
 │gcc-2.953(djgpp)      │0.01319 秒│ 108458 byte │
 │gcc-2.953(cygwin)      │0.01375 秒│ 19169 byte │
 │LSI C-86 Ver 3.30 試食版  │0.04880 秒│ 13564 byte │
 │Turbo C Ver 1.5(small model)│0.02530 秒│ 11008 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌───────────────────────────────┐
 │・プログラムの説明                      │
 │                               │
 │  Fig.1 数字の名前(normal/upside-down)           │
 │                               │
 │  □□□+□□□=□□□−□□□              │
 │  n1 u1 n2 u2 n3 u3 n4 u4              │
 │                               │
 │Fig.1のように数字に名前をつけます。n1〜n4はそのまま見たとき │
 │の数値で、u1〜u4は逆さから見たときの数値です。        │
 │                               │
 │高速化のためにあらかじめ逆さ関係の表Table[]を作成します。例  │
 │えば192を逆さから見ると261なのでTable[192]は261となります。  │
 │逆さから見ると数字にならない場合は0となります。        │
 │                               │
 │n3=n1+n2+n4となることと、3,4,7が逆さにならないことからn3の最 │
 │小値は501、n1,n2,n4の最大値は699であることがわかります。   │
 │                               │
 │プログラムは3重forループで解をカウントします。まず、n3を501 │
 │から999へとループします。そして、表を見てu3を得ます。u3が0な │
 │らばスキップします。そして、さらにn4を101から699へとループし、│
 │同様に表を見てu4を得ます。n3,u3,n4,u4が決まったら、n3-n4が202 │
 │以下だったり、u4-u3が202以下だったりするかを調べます。どちら │
 │かが成立していればn1,n2,u1,u2のいずれかが101未満になり矛盾す │
 │るのでスキップします。                    │
 │                               │
 │次に、n1を101から699へとループし、同様に表を見てu1を得ます。 │
 │この時点でn2とu2もn2=n3-n4-n1とu2=u4-u3-u1の様に決まります。 │
 │和をとっている2数を入れ替えたものを無視するためにn1>n2の場  │
 │合はスキップします。そして、n2とu2が逆さ関係でなければスキ  │
 │ップします。ここまで残ったn1〜n4とu1〜u4ならば、2つの等式を │
 │同時に満たすのでカウントします。               │
 ├───────────────────────────────┤
 │・感想                            │
 │                               │
 │数字を5桁に拡張して問題を解いたところ、35分で118843通りとい  │
 │う結果を得ました。                      │
 └───────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define N 3  /* 1〜5: 桁数を変える場合はこの行を変えるだけでOK */
#define MIN  ( N==1?1 : N==2?11 : N==3?101 : N==4?1001 : 10001  )
#define MAX  ( N==1?9 : N==2?99 : N==3?999 : N==4?9999 : 99999L )
#define MIN2 ( N==1?5 : N==2?51 : N==3?501 : N==4?5001 : 50001U )
#define MAX2 ( N==1?6 : N==2?69 : N==3?699 : N==4?6999 : 69999L )

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int Table[MAX+1]; /* 逆さ関係の表 : 例えば Table[192]=261 となる */
int Count;        /* 解の数 */

/*┌─────────┐
 │逆さ関係の表を作成│
 └─────────┘*/
void MakeTable(void)
{
    /* n:normal  u:upside-down */
    static int ntbl[N][7]={{0,1,2,5,6,8,9}};
    static int utbl[N][7]={{0,1,2,5,9,8,6}};
    int i,j,k=-1,nsum,usum,index[N];

    /* ntbl[]とutbl[]を完成させる.i=1なら10倍,i=2なら100倍... */
    for (i=1;i<N;i++) for (j=1;j<7;j++)
    { ntbl[i][j]=ntbl[i-1][j]*10; utbl[i][j]=utbl[i-1][j]*10; }

    /* 7進数index[]を101〜666へ増やしながらTable[]を作る */
    for (;;) {
        for (i=k+1;i<N;i++) index[i]=(i==0||i==N-1);
        for (nsum=usum=i=0;i<N;i++)
        { nsum+=ntbl[N-1-i][index[i]]; usum+=utbl[i][index[i]]; }
        Table[nsum]=usum;
        for (k=N-1;k>=0;k--) if (index[k]!=6) break;
        if (k!=-1) index[k]++; else break;
    }
}

/*┌─────────────────────────┐
 │パズルを解く(プログラムに引数がなければ等式を表示)│
 └─────────────────────────┘*/
void Solve(int argc)
{
    /*  □□□+□□□=□□□−□□□ n:normal u:upside-down */
    int n1,u1,  n2,u2,  n3,u3,  n4,u4;

    MakeTable(); Count=0;
    for (n3=MIN2;n3<=MAX;n3++) if ((u3=Table[n3])!=0)
     for (n4=MIN;n4<=MAX2;n4++) if ((u4=Table[n4])!=0)
      if  (u4-u3>=MIN*2&&n3-n4>=MIN*2)          /* 差が十分大きい */
       for (n1=MIN;n1<=MAX2;n1++) if ((u1=Table[n1])!=0) {
           n2=n3-n4-n1;
           if (n1>n2) continue;       /* 和の入替えが起これば無視 */
           if  (Table[n2]==0) continue; /* 逆さ数字でなければ無視 */
           u2=u4-u3-u1;
           if  (Table[n2]!=u2) continue;    /* 非逆さ関係なら無視 */
           Count++;                         /* カウントする */
           if (argc==1)   /* プログラムに引数がなければ等式を表示 */
               printf("%7d : %d+%d=%d-%d=%d  %d-%d=%d+%d=%d\n",
                    Count,n1,n2,n3,n4,n1+n2, u4,u3,u2,u1,u4-u3);
       }
}

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

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