整數(shù)對
問題描述 :
Gardon和小希玩了一個游戲，Gardon隨便想了一個數(shù)A（首位不能為0），把它去掉一個數(shù)字以后得到另外一個數(shù)B，他把A和B的和N告訴了小希，讓小希猜想他原來想的數(shù)字。不過為了公平起見，如果小?；卮鸬臄?shù)雖然不是A，但同樣能達到那個條件（去掉其中的一個數(shù)字得到B，A和B之和是N），一樣算小希勝利。而且小希如果能答出多個符合條件的數(shù)字，就可以得到額外的糖果。
所以現(xiàn)在小希希望你編寫一個程序，來幫助她找到盡可能多的解。
例如，Gardon想的是A=31,B=3 告訴小希N=34，
小希除了回答31以外還可以回答27（27+7=34）所以小?？梢砸虼硕玫揭粋€額外的糖果。
輸入:
輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)一行，包含一個數(shù)N(1<=N<=10^9)，文件以0結(jié)尾。
輸出:
對于每個輸入的N，輸出所有符合要求的解（按照大小順序排列）如果沒有這樣的解，輸出"No solution."
樣例輸入:
34 152 21 0
樣例輸出:
27 31 32 126 136 139 141 No solution.
對于這道題，首先讓人想到的便是暴力匹配。從n/2到n依次去掉一個數(shù)字并判斷是否正確。很快編寫好了代碼，當(dāng)然沒有通過，超時了。所以便不得不尋找另外的方法來減少時間。
首先需要意識到的一項是，必須識別出0，這樣會判斷結(jié)束，還要清楚，該樣例的輸入數(shù)據(jù)如果是個位數(shù)，則一定是沒有結(jié)果的。
在不是個位數(shù)的基礎(chǔ)上，對數(shù)據(jù)進行處理。
首先我們假設(shè)數(shù)B是數(shù)A去掉一個數(shù)字以后得到的。則有A+B=n。A中去掉的數(shù)是b，b前面的數(shù)是a，后面的數(shù)是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?？梢钥偨Y(jié)為：A=a*10^（k+1）+b*10^k+c。當(dāng)去掉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的倍數(shù)從0到10的n的位數(shù)次冪。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則不正確，發(fā)生了進位狀況，比原來的b增加了1。比如說，1236去掉3。則b==3，c==6。該方法求得的b中，（2*6）/10=1；所求的b就為4。而在當(dāng)發(fā)生了進位的情況下，a的值是不受影響的，因為就算b是9，進位后是10,10/11=0，a不受影響。
針對這種情況，需要加以判斷處理?？梢韵氲?，對這個數(shù)的a，b，c進行計算得到的n值與鍵入的n值比較，如果相等，則說明該abc符合要求，若不相等，則說明在c的計算時除法進行了舍去，不符合要求。再次尋找其他的組合。
而b的值需要注意的是，該值可能是進位后加一得到的，也可能是沒有進位后得到的。在此需要判斷的是，在格式合法（1-9）的情況下，求得a，并求n與鍵入n比較，相等，則說明，該abc組成的數(shù)A，再和去掉b后的B相加，不需進位就可以得到n。同時，不排除進了一位的情況，仍需要保存后將b減一再進行同樣的運算并加以判斷。
簡單做了代碼描述如下：
a?= (n / k) / 11;
b = (n / k) % 11;
if( ((b? != 0)||(a!=0)) && b < 10)???????????? //((b? != 0)||(a!=0))?判斷該數(shù)是否是個位數(shù)，b==10時，一定發(fā)生了進位情況，且由于b成了兩位數(shù)一定不合要求，所以在此不進行下列計算，直接跳過進行b--運算并判斷是否符合要求。
?{
??? c= (n - b * k - 11 *?a * k) / 2;????????????? //解該情況下的a值
if(n == 2 *?c + b * k + 11 *?a * k)??????????? //判斷能否正確得解，可以得解，則將該A放入數(shù)組。
???? ans[count++] =?c + b * k +?a * 10 * k;
}
b--;????????????????????????????????? //上列的算法是進位后b+1后的狀況，將其減一來計算另一種情況。
?? if( ((b? != 0)||(a!=0)) && b >= 0)????????? //在2*c>10時，A，B兩數(shù)是否符合要求。
?? {
????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)????????? //排除重復(fù)
?????printf(" %d",count[j]);}
???printf("\n");
???}
?}
}
