PAT 1021 Have Fun With Numbers

1023 Have Fun with Numbers

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:

1234567899

Sample Output:

Yes
2469135798

总结：这道题目还是比较简单的，使用高精度乘法计算结果，用一个数组存储原始数字的出现次数，然后将这个数组和相乘的结果作比较，看是否是多出数字或者少了数字（不过代码看着有点多了）

#include 
#include 
using namespace std;
 
vector<int> mul(vector<int> &a,int b){
    int t=0;
    vector<int> c;
    
    for(int i=0;isize() || t;i++){
        if(isize())  t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    
    while(c.size()>1 && c.back()==0)    c.pop_back();
    
    return c;
}
 
int main(){
    string s,w;
    vector<int> a;
    int t[11]={0};
    cin >> s;
    
    for(int i=s.size()-1;i>=0;i--){
        a.push_back(s[i]-'0');
        t[s[i]-'0']++;
    }
    
    auto c=mul(a,2);
    
    bool st=true;
    for(int i=c.size()-1;i>=0;i--){
        t[c[i]]--;
        if(t[c[i]]<0){
            st=false;
            break;
        }
    }
    
    if(st)  puts("Yes");
    else puts("No");
    for(int i=c.size()-1;i>=0;i--)  printf("%d",c[i]);
    
    return 0;
}

 依照惯例，还是看看大佬的代码：

还是那么的简洁明了，通俗易懂！

直接用原始数字的长度进行计算，这样加入有进位的话，最后flag（表示进位值）会等于1，如果没有进位的话，如果数字不一样flag1会等于1，最后就能判断 Yes 还是 No 了

#include 
#include 
using namespace std;
int book[10];
int main() {
    char num[22];
    scanf("%s", num);
    int flag = 0, len = strlen(num);
    for(int i = len - 1; i >= 0; i--) {
        int temp = num[i] - '0';
        book[temp]++;
        temp = temp * 2 + flag;
        flag = 0;
        if(temp >= 10) {
            temp = temp - 10;
            flag = 1;
        }
        num[i] = (temp + '0');
        book[temp]--;
    }
    int flag1 = 0;
    for(int i = 0; i < 10; i++) {
        if(book[i] != 0)
            flag1 = 1;
    }
    printf("%s", (flag == 1 || flag1 == 1) ? "No\n" : "Yes\n");
    if(flag == 1) printf("1");
    printf("%s", num);
    return 0;
}

好好学习，天天向上！

我要考研！