PTA甲级——1023

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:

1
1234567899

Sample Output:

1
2
Yes
2469135798

思路

​ 大致题意：给出一个数，将这个数乘2得到一个数，对得到的这个数中各个位上的数出现次数和原来的那个数应该一致，有一种思路就是可以分别统计一下乘2前后的数0～9分别出现的次数比较即可。还有一种思路就是乘2之后得到的数进行一个string排序比较一下是否相同即可。

代码一

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n;
int st[10];

int main()
{
    string s;
    cin >> s;
    int c = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        st[s[i] - '0']++;
    }
    
    for (int i = s.length() - 1; i >= 0; i--) {
        int k = (s[i] - '0') * 2  + c;
        s[i] = char('0' + k % 10);
        c = k / 10;
    }
    if (c) s.insert(0,to_string(c));
    // cout << s;
    bool flag = false;
    for(int i = 0; i <= 9; i++) {
        if (st[i]) {
            int k = 1;
            for (int j = 0; j < s.length(); j++){
                if (s[j] == (i + '0')) {
                    k++;
                }
            }
            if (st[i] == k){
                cout << "No\n";  
                for (int i = 0; i < s.length(); i++) cout << s[i]; 
                return 0;
            } 
        } else {
            for (int j = 0; j < s.length(); j++){
                if (s[j] == (i + '0')) {
                    cout << "No\n";
                    for (int i = 0; i < s.length(); i++) cout << s[i]; 
                    return 0;
                }
            }
        }
        
    }

    cout << "Yes\n";
    for (int i = 0; i < s.length(); i++) cout << s[i];
    
    return 0;
}

代码二

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n;

int main()
{
    string s, ss;
    cin >> s;
    ss = s;
    int c = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        st[s[i] - '0']++;
    }
    
    for (int i = s.length() - 1; i >= 0; i--) {
        int k = (s[i] - '0') * 2  + c;
        s[i] = char('0' + k % 10);
        c = k / 10;
    }
    if (c) s.insert(0,to_string(c));
    string sss = s;
    sort(sss.begin(), sss.end());
    sort(ss.begin(), ss.end());
    if (sss == ss) cout << "Yes\n";
    else cout << "No\n";

    cout << s;
    return 0;
}