PAT A1023 Have Fun with Numbers

PAT A1023 Have Fun with Numbers

Sample Input:

1234567899

Sample Output:

Yes
2469135798

• 思路 1：大整数运算
  用string 模拟大整数倍乘，再判断结果是否为原数的一个permutation(使用has[10]先++再–，最后看结果是否==0)

• code 1：

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
vector<char> v, v2; 
string Double(string s){
	int carry = 0;
	string ans = s;
	for(int i = s.size()-1; i >= 0; --i){
		int a = s[i] - '0';
		ans[i] = (a * 2 + carry) % 10 + '0';
		carry = (a * 2 + carry) / 10;
	}
	if(carry > 0) ans.insert(0, "1");
	return ans;
}
int has[10];
bool is_permutation(string a, string b){
	if(a.size() != b.size()) return false;
	for(int i = 0; i < a.size(); ++i){
		has[a[i]-'0']++;
	} 
	for(int i = 0; i < a.size(); ++i){
		has[b[i]-'0']--;
	}	
	for(int i = 0; i < a.size(); ++i){
		if(has[i] != 0) return false;
	}
	return true;
}
int main(){
	string s;
	cin >> s;
	string dou = Double(s);
	printf("%s\n%s\n", is_permutation(s, dou) ? "Yes" : "No", dou.c_str());
	return 0; 
} 

• 思路 2：
  使用algorithm中自带的is_permutation(it1.begin(), it1.end(), it2.begin())函数：

• code 2:

#include <iostream>
#include <algorithm>	// is_permutation
using namespace std;
string Double(string s){
	int carry = 0;
	string ans = s;
	for(int i = s.size()-1; i >= 0; --i){
		int a = s[i] - '0';
		ans[i] = (a * 2 + carry) % 10 + '0';
		carry = (a * 2 + carry) / 10;
	}
	if(carry > 0) ans.insert(0, "1");
	return ans;
}
int main(){
	string s;
	cin >> s;
	string dou = Double(s);
	printf("%s\n%s\n", is_permutation(s.begin(), s.end(), dou.begin()) ? "Yes" : "No", dou.c_str());
	return 0; 
} 

• T3 code:

#include <bits/stdc++.h>
using namespace std;

string Double(string s)
{
    int carry = 0;
    string ans = s;
    for(int i = s.size()-1; i >= 0; --i)
    {
        ans[i] = ((s[i] - '0') * 2 + carry) % 10 + '0';
        carry = ((s[i] - '0') * 2 + carry) / 10;
    }
    if(carry > 0) ans.insert(0, "1");
    return ans;
}
bool Is_per(string s1, string s2)
{
    if(s1.size() != s2.size())
    {
        return false;
    }else
    {
        vector<int> has1(s1.size()+1), has2(s2.size()+1);
        for(int i = 0; i < s1.size(); ++i)
        {
            has1[s1[i]-'0']++;
        }
        for(int i = 0; i < s2.size(); ++i)
        {
            has2[s2[i]-'0']++;
        }
        return has1 == has2 ? true : false;
    }
}
int main()
{
    string num;
    cin >> num;
    string res = Double(num);
//    if(is_permutation(res.begin(), res.end(), num.begin()))
    if(Is_per(num, res))
    {
        printf("Yes\n");
    }else
    {
        printf("No\n");
    }
    cout << res;
    return 0;
}