00-自测4. Have Fun with Numbers (20)

Posted on   |   In   |  

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.

1
2
3
4
5
Sample Input:
1234567899
Sample Output:
Yes
2469135798

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

string Compute(string str)
{
    int addPos = 0;     //进位
    string strReverse;
    for(int i = str.size() - 1; i >= 0 ; --i)
    {
        int result = (str[i] - '0') * 2 + addPos;
        if(result > 9)
        {
            result -= 10;
            addPos = 1;
        }
        else
        {
            addPos = 0;
        }
        strReverse += (result + '0');
    }
    if(1 == addPos)
    {
        strReverse += '1';
    }
    return strReverse;
}

bool Compare(char a, char b)
{
    return a > b;
}

bool Check(string str1, string str2)
{
    if(str1.size() != str2.size())
    {
        return false;
    }
    else
    {
        vector<char> cvec1, cvec2;
        for(int i = 0; i < str1.size(); ++i)
        {
            cvec1.push_back(str1[i]);
            cvec2.push_back(str2[i]);
            sort(cvec1.begin(), cvec1.end(),Compare);
            sort(cvec2.begin(),cvec2.end(),Compare);
        }
        for(int i = 0; i < cvec1.size(); ++i)
        {
            if(cvec1[i] != cvec2[i])
            {
                return false;
            }
        }
        return true;
    }

}


int main()
{
    string str;
    cin >> str;
    string result;
    result = Compute(str);
    if(Check(str,result))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    for(int i = result.size() - 1; i >= 0; --i)
    {
        cout << result[i];
    }
    cout << endl;
    return 0;
}

代码不难，即使在自己电脑上调，也就改了一次后就直接往PAT上测试了，然后就AC了，今晚运气不错加上前四道自测题不难，基本上没有超过第二遍的，最后一道自测题还没看，11点多开始写自测题1，到现在不到两小时写出前四道，对我这新手来说还算一般。最后一道自测题等考完试在看吧。该洗洗睡了！

测试结果如下：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 264 3/3
1 答案正确 1 180 2/2
2 答案正确 1 308 2/2
3 答案正确 1 180 2/2
4 答案正确 1 264 2/2
5 答案正确 1 308 3/3
6 答案正确 1 308 3/3
7 答案正确 1 180 3/3