题目

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 diferent 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.

Sample Input:

1234567899

Sample Output:

Yes

2469135798

题目分析

已知一个最多20位的数字N，判断N乘2后的数字M是否只是组成N的各位数字的重新排列

解题思路

用一个数组记录N中各位数字出现的次数，乘2后的数字M中出现相同数字则出现次数减一（该判断隐含M和N的长度不相等的情况，长度不相等则出现次数一定不相等，数组中出现次数不相等时元素值不为0）
大整数相乘算法

易错点

字符和数字的转换（字符-'0'=数字）

知识点

字符串转换

#include <algorithm>

reverse(ds.begin(),ds.end());

Code

Code 01

#include <iostream>

#include <algorithm>

using namespace std;

int main(int argc,char * argv[]) {

	string s,ds;

	cin>>s;

	int sf[10]= {0},carry=0;

	for(int i=s.length()-1; i>=0; i--) {

		sf[s[i]-'0']++;

		int temp=(s[i]-'0')*2+carry;

		ds.push_back(temp%10+'0');

		carry=temp/10;

		sf[temp%10]--;

	}

	while(carry!=0) {

		ds.push_back(carry%10+'0');

		sf[carry%10]--;

		carry/=10;

	}

	bool flag = true;

//	strrev(s.c_str());

//	if(ds.length()!=s.length())flag=false;

//	else {}

	for(int i=0; i<10; i++) {

		if(sf[i]!=0) {

			flag = false;

			break;

		}

	}

	printf("%s", flag? "Yes\n" : "No\n");

	reverse(ds.begin(),ds.end());

	printf("%s",ds.c_str());

	return 0;

}

Code 02

#include <cstdio>

#include <string.h>

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;

}

巴特西

PAT Advanced 1023 Have Fun with Numbers (20) [⼤整数运算]

题目

题目分析

解题思路

易错点

知识点

Code

Code 01

Code 02

最新文章

热门文章