1023 Have Fun with Numbers (20)

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;
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值