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 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
解题思路:
判断一个不超过20位的整数在乘2以后是否是原数字的另一个排列。柳神博客使用了打表的方法,比较直观易懂,要注意最后可能的进位。
算法笔记使用了大整数运算,代码较长。
#include<cstdio>
#include<cstring>
#include<cmath>
int book[10]={0};
int main(){
char str[25];
int ans[25];
bool flag=true;
int temp,carry=0;
int k=0;
scanf("%s",str);
int len=strlen(str);
for(int i=len-1;i>=0;i--){
temp=str[i]-'0';
book[temp]++;
temp=temp*2+carry;
ans[k]=temp%10;
carry=temp/10;
book[ans[k]]--;
k++;
}
if(carry!=0)
ans[k++]=1;
for(int i=0;i<=k;i++){
if(book[i]!=0)
flag=false;
}
if(flag==true)
printf("Yes\n");
else
printf("No\n");
for(int i=k-1;i>=0;i--){
printf("%d",ans[i]);
}
return 0;
}
//大整数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30;
struct node{
int d[maxn];
int len;
node(){
memset(d,0,sizeof(d));
len=0;
}
};
node change(char str[]){
node a;
a.len =strlen(str);
for(int i=0;i<a.len;i++){
a.d[i]=str[a.len -1-i]-'0';
}
return a;
}
node multi(node a,int p){
node c;
int array=0;
for(int i=0;i<a.len ;i++) {
int x=a.d[i]*p+array;
c.d[c.len ++]=x%10;
array=x/10;
}
while(array!=0){
c.d[c.len++]=array;
array/=10;
}
return c;
}
bool judge(node a,node b){
if(a.len !=b.len ) return false;
int count[10]={0};
for(int i=0;i<a.len ;i++){
count[a.d[i]]++;
count[b.d[i]]--;
}
for(int i=0;i<10 ;i++){
if(count[i]!=0)
return false;
}
return true;
}
void show(node a){
for(int i=a.len-1;i>=0;i--)
printf("%d",a.d[i]);
}
int main(){
char str1[maxn];
gets(str1);
node a=change(str1);
node mul=multi(a,2);
if(judge(a,mul)==true) printf("Yes\n");
else printf("No\n");
show(mul);
return 0;
}