pairs of integers(构造).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
    int v,len;
    bool operator < (const node & t) const {
        return v < t.v;
    }
}ans[110];
int ans_pos;
int n,len;
int e10[15];
int dig[15];
char n1[15],n2[15];
int num[15];

void dfs(int pos)
{
    int temp[15], temp2[15];
    int i,j,t;

    memcpy(temp, num,sizeof(num));
    memcpy(temp2, dig,sizeof(num));
    if (pos == len-1) {
        if (dig[pos] < 0) {
            return ;
        }
        if (num[ n1[pos] -'A'] != -1) {
            if (num[ n1[pos] -'A'] != dig[pos]) {
                return ;
            }
        }
        else {
            num[ n1[pos] -'A'] = dig[pos];
        }
        if (num[0] == 0 && n2[len-2] != 'A') {
            goto recover;
        }
        //make num
        i = 0;
        ans[ans_pos].len = len;
        while (num[i] == 0) {
            ans[ans_pos].len --;
            i ++;
        }
        t = 0;
        for (i=0;i<len;i++) {
            t += e10[i] * num[len-i-1];
        }
        ans[ans_pos ++].v = t;
        goto recover;
    }

    //carry
    if (dig[pos] < 0) {
        dig[pos] += 10;
        dig[pos +1] --; 
    }
    //select one branch to cal
    if (n1[pos] == n2[pos]) {//same
        if (num[ n1[pos] -'A'] != -1) {//be valued
            if (num[ n1[pos] -'A'] * 2 >= 10) {//have carry
                dig[pos+1] --;
            }
            dfs(pos+1);
        }
        else if (dig[pos] % 2 == 0) {//can be divied
            num[ n1[pos] -'A'] = dig[pos] / 2;
            dfs(pos+1);

            num[ n1[pos] -'A'] = (10+ dig[pos]) / 2;
            if (num[ n1[pos] -'A'] >= 10) {
                goto recover ;
            }
            dig[pos+1] --;
            dfs(pos+1);
        }
        else {
            goto recover ;
        }
    }
    else {//not same
        if (num[ n1[pos] -'A'] != -1) {//n1 be valued
            if (num[ n2[pos] -'A'] != -1) {//all be valued
                if (dig[pos] != num[ n1[pos] -'A'] + num[ n2[pos] -'A']) {
                    goto recover ;
                }
                dfs(pos+1);
            }
            else {//n2 not be valued
                if (dig[pos] >= num[ n1[pos] -'A']) {
                    num[ n2[pos] -'A'] = dig[pos] - num[ n1[pos] -'A'];
                    dfs(pos+1);
                }

                num[ n2[pos] -'A'] = 10+dig[pos] - num[ n1[pos] -'A'];
                if (num[ n2[pos] -'A'] >= 10) {
                    goto recover ;
                }
                dig[pos+1] --;
                dfs(pos+1);
            }
        }
        else {//n1 not be valued
            if (num[ n2[pos] -'A'] == -1) {//all not be valued
                for (i=0;i<10;i++) {//enum
                    num[ n1[pos] -'A'] = i;
                    if (num[ n1[pos] -'A'] <= dig[pos]) {
                        num[ n2[pos] -'A'] = dig[pos] - num[ n1[pos] -'A'];
                        dfs(pos+1);
                    }

                    t = num[ n2[pos] -'A'];
                    num[ n2[pos] -'A'] = 10+dig[pos] - num[ n1[pos] -'A'];
                    if (num[ n2[pos] -'A'] >= 10) {
                        num[ n2[pos] -'A'] = t;
                        continue ;
                    }
                    dig[pos+1] --;
                    dfs(pos+1);
                    dig[pos+1] ++;
                }
            }
            else {//n2 be valued
                if (dig[pos] > num[ n2[pos] -'A']) {
                    num[ n1[pos] -'A'] = dig[pos] - num[ n2[pos] -'A'];
                    dfs(pos+1);
                }
                num[ n1[pos] -'A'] = 10+dig[pos] - num[ n2[pos] -'A'];
                if (num[ n2[pos] -'A'] >= 10) {
                    goto recover ;
                }
                dig[pos+1] --;
                dfs(pos+1);
            }
        }
    }
recover:
    memcpy(num ,temp,sizeof(num));
    memcpy(dig ,temp2,sizeof(num));
    return ;
}

int main()
{
    int i,j,k,t;
    e10[0] =1;
    for (i=1;i<=10;i++) {
        e10[i] = 10 * e10[i-1];
    }

    while (scanf("%d", &n)==1) {
        if(n == 0) {
            break ;
        }
        len = 0;
        t = n;
        while (t) {
            dig[len ++] = t%10;
            t /= 10;
        }
        for (i=0;i<len;i++) {
            n1[i] = 'A'+i;
            n2[i] = '0';
            num[i] = -1;
        }
        reverse(n1,n1+len);
        ans_pos = 0;
        
        for (i=0;i<len;i++) {
            j = 0;
            for (k=len-1;k>=0;k--) {
                if (k == i) {
                    continue ;
                }
                n2[j ++] = k + 'A';
            }
            dfs(0);
        }
        sort(ans, ans+ans_pos);
        if (ans_pos == 0) {
            puts("0");
        }
        else {
            int unique = 1;
            for (i=1;i<ans_pos;i++) {
                if (ans[i].v != ans[i-1].v) {
                    unique ++;
                }
                else {
                    ans[i-1].v = -1;
                }
            }
            printf("%d\n", unique);
            for (i=0;i<ans_pos;i++) {
                if (ans[i].v != -1) {
                    printf ("%d + %0*d = %d\n", ans[i].v, ans[i].len-1, n-ans[i].v, n);
                }
            }
        }
    }
}