1023 Have Fun with Numbers (20分)

1 题目

1023 Have Fun with Numbers (20分)
Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!

Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.

Input Specification:
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.

Output Specification:
For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.

Sample Input:
1234567899Sample Output:
Yes
2469135798

2 解析

2.1 题意

判断这个数a和它的两倍的数c中是否所有数字出现的次数相同（相同排列），如果是则输出Yes，否则输出No，然后输出数c。

2.2 思路

由于数字的长度达到20位，因此需要用高精度与低精度的乘法，计算乘积后的结果，然后比较两个数中0～9每个数字出现的次数，如果相同则输出Yes，否则输出No。

3 参考代码

#include <cstdio>
#include <cmath>
#include <cstring>const int MAXN = 25;
int cnt1[10], cnt2[10];struct bign
{int d[1000];int len;bign(){memset(d, 0, sizeof(d));len = 0;}};bign change(char str[]){bign a;a.len = strlen(str);for (int i = 0; i < a.len; ++i){a.d[i] = str[a.len - 1 -i] - '0';cnt1[a.d[i]]++;//统计a每个数字出现的次数}return a;
}bign multi(bign a, int b){bign c;int carry = 0;for (int i = 0; i < a.len; ++i){int temp = carry + a.d[i] * b;c.d[c.len++] = temp % 10;carry = temp/10;}while(carry != 0){c.d[c.len++] = carry % 10;carry /= 10;}return c;
}void print(bign a){for (int i = a.len - 1; i >= 0; --i){printf("%d", a.d[i]);}
}void judge(bign a, bign c){if(a.len != c.len){//长度不想等，c肯定不是a的排列printf("No\n");}else{for (int i = 0; i < c.len; ++i)//统计c每个数字出现的次数{cnt2[c.d[i]]++;}int i;for (i = 0; i < 10; ++i){if(cnt1[i] != cnt2[i]){//如果出现数字出现的次数不想等的情况，c肯定不是a的排列printf("No\n");break;}}if(i == 10){//如果循环判定完都没有出现不想等数字出现的次数，c是a的排列printf("Yes\n");}}
}int main(int argc, char const *argv[])
{memset(cnt1, 0, sizeof(cnt1));memset(cnt2, 0, sizeof(cnt2));char str[25];scanf("%s", str);bign a = change(str);bign c = multi(a,2);judge(a,c);print(c);return 0;
}