Pairs of Integers

You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The first integer always has at least two digits and starts with a non-zero digit. The second integer always has one digit less than the first integer and may start with a zero digit.

Input

The input consists of a single integer N (10 ≤ N ≤ 10 ⁹).

Output

Write the total number of different pairs of integers that satisfy the problem statement. Then write all those pairs. Write one pair on a line in ascending order of the first integer in the pair. Each pair must be written in the following format:

X + Y = N

Here X, Y, and N must be replaced with the corresponding integer numbers. There should be exactly one space on both sides of '+' and '=' characters.

Example

input	output
302	5 251 + 51 = 302 275 + 27 = 302 276 + 26 = 302 281 + 21 = 302 301 + 01 = 302

//题意是，给出一个数，问有哪些数少掉某一位，与原数相加可得这个数，列出所有情况，第一个加数不能有前导 0 ，后一个可以有，

还有，重复的情况只能输出一个比如 455 + 55 = 510 去掉 455 第一个5，和第二个5都能得510 ，只要输出一次就可以了

//做过类似的题目，用数学方法做，比较快。http://www.cnblogs.com/haoabcd2010/p/5991009.html

不过这题有点不一样，要按第一个数大小排序，还要去掉重复的，还要记得在第二个加数可能要补0 ，不过这都是些小问题。。。

15ms 比较快

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct Num
 7 {
 8     int a,b;
 9     int z;
10 }num[1000];
11 int t;
12 
13 bool cmp(Num x,Num y)
14 {
15     return x.a<y.a;
16 }
17 
18 void read(int x,int y)
19 {
20     int a=x,b=y;
21     int lenx=0,leny=0;
22     while (a!=0)
23     {
24         lenx++;
25         a/=10;
26     }
27     while (b!=0)
28     {
29         leny++;
30         b/=10;
31     }
32     if (y==0) leny=1;
33     num[t].a=x;
34     num[t].b=y;
35     num[t].z=lenx-1-leny;
36     t++;
37 }
38 
39 int main()
40 {
41     int N;
42     while (scanf("%d",&N)!=EOF)
43     {
44         t=0;
45         for (int i=1;i<=N;i*=10)
46         {
47             int a=N/i/11;
48             int b=N/i%11;
49 
50             if (b<10)
51             {
52                 int c=(N-N/i*i)/2;
53                 if ((11*a+b)*i+2*c==N)
54                     read( (10*a+b)*i+c , a*i+c );
55             }
56             b--;
57             if (a+b&&b>=0)
58             {
59                 int c=(N-N/i*i+i)/2;
60                 if ((11*a+b)*i+2*c==N)
61                     read( (10*a+b)*i+c , a*i+c );
62             }
63         }
64         sort(num,num+t,cmp);
65         int real_t=0;
66         for (int i=0;i<t;i++)
67         {
68             if (i!=0&&num[i].a==num[i-1].a) continue;
69             real_t++;
70         }
71         printf("%d
",real_t);
72         for (int i=0;i<t;i++)
73         {
74             if (i!=0&&num[i].a==num[i-1].a) continue;
75             printf("%d + ",num[i].a);
76             for (int j=0;j<num[i].z;j++)
77                 printf("0");
78             printf("%d = %d
",num[i].b,N);
79         }
80     }
81     return 0;
82 }

View Code