PAT A1023

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 file 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:
1234567899
Sample Output:
Yes
2469135798

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include "stdio.h"
//#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "algorithm"
using namespace std;
//typedef long long LL;
const int maxn = 100010;
struct bign{
int d[1000],len;
bign(){
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(char str[]){
bign a;
a.len = (int)strlen(str);
for (int i = 0; i < a.len ; i++) {
a.d[i] = str[a.len - 1 - i] - '0';
}
return a;
}
bign multi(bign a, int b){
int carry = 0;
bign c;
for (int i = 0 ; i < a.len; i++) {
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10;//个位作为该位结果
carry = temp / 10;//高位部分作为新的进位
}
while (carry) {//和加法不一样,乘法的进度可能不止一位,因此用while
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
bool Judge(bign a,bign b){
if (a.len != b.len) return false;//长度不同
int count[10] = {0};
for (int i = 0; i < a.len; i++) {
count[a.d[i]]++;//对应位置+1
count[b.d[i]]--;//对应位置-1
}
for (int i = 0; i < 10; i++) {
if (count[i]) {
return false;
}
}
return true;
}
void print(bign a){
//输出bign
for (int i = a.len -1; i >= 0; i--) {
printf("%d", a.d[i]);
}
}
bool hashTable[10] = {true};
int main(){
char stra[21];
scanf("%s", stra);
bign a = change(stra);
bign mul = multi(a, 2);
if (Judge(a, mul)) {
printf("Yes\n");
}else {
printf("No\n");
}
print(mul);

return 0;
}