整数对

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3049    Accepted Submission(s): 1064

Problem Description

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）所以小希可以因此而得到一个额外的糖果。

 

 

Input

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

 

 

Output

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

 

 

Sample Input

34 152 21 0

 

 

Sample Output

27 31 32 126 136 139 141 No solution.

 

 

Author

Gardon

 

题解：数学题，暴力果断超时，看了网上的思路，是把这个数分为上中下三部分，从N推出答案；注意考虑2*a是否进位；

A == a + b * 10^k + c * 10^(k+1)

B == a         +         c * 10^k

N == A + B == 2 * a + b * 10^k + c * 10^k * 11

推出：

c=N/(11*k);

b=N/k-c*11;

a=(N-b*k-11*k*c)/2;

ans=a+b*k+c*k*10;

ac代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int INF=0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))#define SI(x) scanf("%d",&x)#define PI(x) printf("%d",x)#define P_ printf(" ")int ans[100010];int main(){ int N,a,b,c,k; while(SI(N),N){ int tp=0; for(k=1;k<=N;k*=10){ c=N/(11*k); b=N/k-c*11; if(b+c&&b<10){ a=(N-b*k-11*k*c)/2; if(2*a+b*k+11*k*c==N)ans[tp++]=a+b*k+c*k*10; } b--; if(b+c&&b>=0){ a=(N-b*k-11*k*c)/2; if(2*a+b*k+11*k*c==N)ans[tp++]=a+b*k+c*k*10; } } if(!tp){ puts("No solution.");continue; } sort(ans,ans+tp); k=unique(ans,ans+tp)-ans; for(int i=0;i
          
         
        
       
      
     

　暴力超时代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int INF=0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))#define SI(x) scanf("%d",&x)#define PI(x) printf("%d",x)#define P_ printf(" ")int a[10];int ans[100010];int main(){ int N,k,t,c,temp,tp; while(SI(N),N){ t=N;k=0; while(t){ k++;t/=10; } tp=0; for(int i=pow(10,k-1);i
           
            =0;j--){ temp=0; for(int l=c-1;l>=0;l--){ if(l==j)continue; temp=temp*10+a[l]; } // printf("%d\n",temp); if(temp+i==N){ ans[tp++]=i;break; } } } if(!tp)puts("No solution."); else for(int i=0;i