整数对

问题描述 :

Gardon和小希玩了一个游戏，Gardon随便想了一个数A（首位不能为0），把它去掉一个数字以后得到另外一个数B，他把A和B的和N告诉了小希，让小希猜想他原来想的数字。不过为了公平起见，如果小希回答的数虽然不是A，但同样能达到那个条件（去掉其中的一个数字得到B，A和B之和是N），一样算小希胜利。而且小希如果能答出多个符合条件的数字，就可以得到额外的糖果。

所以现在小希希望你编写一个程序，来帮助她找到尽可能多的解。

例如，Gardon想的是A=31,B=3 告诉小希N=34，

小希除了回答31以外还可以回答27（27+7=34）所以小希可以因此而得到一个额外的糖果。

输入:

输入包含多组数据，每组数据一行，包含一个数N(1<=N<=10^9)，文件以0结尾。

输出:

对于每个输入的N，输出所有符合要求的解（按照大小顺序排列）如果没有这样的解，输出"No solution."

样例输入:

34
152
21
0

样例输出:

27 31 32
126 136 139 141
No solution.

对于这道题，首先让人想到的便是暴力匹配。从n/2到n依次去掉一个数字并判断是否正确。很快编写好了代码，当然没有通过，超时了。所以便不得不寻找另外的方法来减少时间。

首先需要意识到的一项是，必须识别出0，这样会判断结束，还要清楚，该样例的输入数据如果是个位数，则一定是没有结果的。

在不是个位数的基础上，对数据进行处理。

首先我们假设数B是数A去掉一个数字以后得到的。则有A+B=n。A中去掉的数是b，b前面的数是a，后面的数是c。举例：1236去掉2，a=1，c=36。去掉6，a=123，c=0；则第一个例子可以写成1236=1*10^3+2*10^2+36*10^0。第二个例子：1236=123*10^1+6*10^0。可以总结为：A=a*10^（k+1）+b*10^k+c。当去掉b之后，B=a*10^k+c。

按此看来，n=A+B=（11*a+b）*10^k+c*2。在计算a，b，c时，可以把n进行对10^k做商后再对11取商和取余后得到。

这样的计算，有a=(n/k)/11；k是10的倍数从0到10的n的位数次幂。b=（n/k）%11。但是把式子写开来，就变成了：a=（（11*a+b）*10^k+c*2）/（（10^k）/11）

即：（11*a+b+（2*c）/10^k）/11。b=（11*a+b+（2*c）/10^k）%11。此时，若（2*c）/10^k若不为零，则所求的b则不正确，发生了进位状况，比原来的b增加了1。比如说，1236去掉3。则b==3，c==6。该方法求得的b中，（2*6）/10=1；所求的b就为4。而在当发生了进位的情况下，a的值是不受影响的，因为就算b是9，进位后是10,10/11=0，a不受影响。

针对这种情况，需要加以判断处理。可以想到，对这个数的a，b，c进行计算得到的n值与键入的n值比较，如果相等，则说明该abc符合要求，若不相等，则说明在c的计算时除法进行了舍去，不符合要求。再次寻找其他的组合。

而b的值需要注意的是，该值可能是进位后加一得到的，也可能是没有进位后得到的。在此需要判断的是，在格式合法（1-9）的情况下，求得a，并求n与键入n比较，相等，则说明，该abc组成的数A，再和去掉b后的B相加，不需进位就可以得到n。同时，不排除进了一位的情况，仍需要保存后将b减一再进行同样的运算并加以判断。

简单做了代码描述如下：

a = (n / k) / 11;
b = (n / k) % 11;
if( ((b  != 0)||(a!=0)) && b < 10)             //((b  != 0)||(a!=0)) 判断该数是否是个位数，b==10时，一定发生了进位情况，且由于b成了两位数一定不合要求，所以在此不进行下列计算，直接跳过进行b--运算并判断是否符合要求。
 {
    c= (n - b * k - 11 * a * k) / 2;              //解该情况下的a值
if(n == 2 * c + b * k + 11 * a * k)            //判断能否正确得解，可以得解，则将该A放入数组。
     ans[count++] = c + b * k + a * 10 * k;
}
b--;                                  //上列的算法是进位后b+1后的状况，将其减一来计算另一种情况。
   if( ((b  != 0)||(a!=0)) && b >= 0)          //在2*c>10时，A，B两数是否符合要求。
   {
    c = (n - b * k - 11 *a * k) / 2;
if(n == 2 * c + b * k + 11 * a * k)                //计算并判断
ans[count++] = c + b * k + a* 10 * k;
}

AC的代码如下：

#include <stdio.h>
#include<stdlib.h> 
int count[100];

int cmp(const void *p1,const void *p2)
{
    return *((int*)p2)<*((int*)p1)?1:-1;
}
void main()
{
 int a,b,c,k,n,i,j;
 while(scanf("%d",&n)!=EOF&&n)
 {
  i=0;
  for (k=1;k<=n;k=k*10)
  {
   b=(n/k)%11;
   a=(n/k)/11;
   if ((a!=0||b!=0)&&b<10)
   {
    c=(n-(11*a+b)*k)/2;
    if(n==11*k*a+b*k+2*c)
    {
     count[i++]=10*k*a+k*b+c;
    }
   }
   b--;
   if((a!=0||b!=0)&&b>=0)
   {
    c=(n-(11*a+b)*k)/2;
    if(n==11*k*a+b*k+2*c)
    {
     count[i++]=10*k*a+k*b+c;
    }
   }
  }
  if (i==0)
    printf("No solution.\n");
   else
   {
    qsort(count,i,sizeof(int),cmp);          //排序处理
    printf("%d",count[0]);
    for (j=1;j<i;j++)
    {
     if(count[j]!=count[j-1]&&j>0)          //排除重复
     printf(" %d",count[j]);}
   printf("\n");
   }
 }
}