7-4 Have Fun with Numbers

Topic describes:

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.

注意，123456789是一个9位数字，由1到9组成，没有重复。将其翻倍，得到246913578，它恰好是另一个9位数字，由1到9组成，只是排列不同。看看结果，如果我们再加倍!

现在你应该检查是否有更多的数字与这个属性。也就是说，一个给定的数字的两倍，你要告诉结果的数字是否只由原数字中的数字的一个排列组成。

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

Train of thought:

? 此题先给我们一个数x1，让我们将其乘以2，得到另一个数x2。让我们判断这两个数的数字组成是否相同。

? 我们考虑到这是个最多有20位的数字，因此我们可以用数组来存放这两个数。

? 那我们如何判断它们的数字组成是否相同呢？我们可以另外设两个含十个元素的数组，数组的下标从0 ~ 9，分别表示数字0~9的状态。这两个数组可以分别表示x1和x2中0 ~ 9的状态，如果这两个数组中0~9的状态一致，则符合题意。

code:

#include 
#include 
#include 
using namespace std;

char arr1[30];//初始数
char arr2[30];//乘以二之后的数
int st1[20];//表示arr1的状态
int st2[20];//表示arr2的状态

int main() 
{
	cin >> arr1;
	int len1 = strlen(arr1);
	int m = 0;//m代表进位
	for (int i = len1 - 1; i >= 0; i--)//计算arr2，并以字符的形式存入数组
	{
		if (arr1[i] < '5' && arr1[i] >= '0')
		{
			arr2[i] = ((arr1[i] - '0') * 2 + m)+'0';
			m = 0;
		}
		else
		{
			arr2[i] = ((arr1[i] - '0') * 2 - 10 + m)+'0';
			m = 1;
		}
	}
    //跳出循环后m表示的是初始数乘以二后最高位是否进位
	if (m == 1)//若进位，则最大只能进1位，所以arr2中多了一位，并且一定是1
	{
		st2[1] = 1;//表示arr2中存在数字1
	}
	for (int i = 0; i <= len1 - 1; i++)//判断arr1和arr2中0~9的状态
	{
		st1[arr1[i]-'0'] = 1;
		st2[arr2[i]-'0'] = 1;
	}
	for (int i = 0; i <= len1 - 1; i++)//arr1和arr2中数字的状态是否相同
	{
		if (st1[i] != st2[i])//不相同，直接输出arr2然后结束程序
		{
			cout << "No" << endl;
			if (m == 1)//注意还要在最前面（最高位）输出进位
			{
				cout << 1;
			}
			cout << arr2;
			return 0;
		}
	}
    //循环结束，代表状态相同
	cout << "Yes" << endl;
	if (m == 1)
	{
		cout << 1;
	}
	cout << arr2;
	return 0;
}
刷题日记

相关

标签