1023 Have Fun with Numbers (20 point(s))

1023 Have Fun with Numbers (20 point(s))

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 <iostream>
#include <unordered_map> // map 会按照键的大小排序，unsorted_map 不会

using namespace std;

unordered_map<int, int> M;

int main(){
    
    string s;
    cin>>s;  //因为数字可能长达二十位，long long 8byte 64 位，为20位数字：18XXXXXXXXX……。不及20位十进制的。故用字符串保留输入
    // 31244 收到的整数
    // 01234 在 string 里的下标
    // 43210 用 digit 数组保存的下标，通常高位对应高下标
    int digit[21] = {0}; //因为20位的数字可能进位到21位，所以大小要设置为21.
    for(int i=s.size()-1;i>=0;i--){ // string 接收整数，digit 数组保存
        digit[s.size()-1-i]=s[i]-'0';
        M[digit[s.size()-1-i]]++;
    }
    int carry = 0; // 进位
    for(int i=0;i<s.size();i++){
        digit[i] = digit[i] * 2 + carry;
        if(digit[i]<10)carry=0;
        if(digit[i]>=10){
            digit[i]-=10;
            carry=1;
        }
        M[digit[i]]--;
        if(M[digit[i]] == 0) M.erase(digit[i]);
    }
    if(carry == 1){  // 最高位进位了
        digit[s.size()] = 1;
        M[1]--;
        if(M[1] == 0) M.erase(1);
    }
    
    if(M.size() == 0){ 
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    
    if(digit[s.size()] != 0) cout<<digit[s.size()];  //最高位进位情况
    for(int i=s.size()-1;i>=0;i--) cout<<digit[i];
    
    
}