1010. Radix

2017-11-02

英文描述

Radix (25)
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is “yes”, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number “radix” is the radix of N1 if “tag” is 1, or of N2 if “tag” is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print “Impossible”. If the solution is not unique, output the smallest possible radix.
Sample Input:1
6 110 1 10
Sample Output:1
2
Sample Input:2
1 ab 1 2
Sample Output:1
Impossible

中文描述

进制
给出一对正整数，比如6和110，这个等式6=100是对的吗？答案是肯定的，如果6是一个十进制数且110是一个二进制数。
现在对于任何一对正整数N1和N2，你的任务的发现一个数字的进制然而它是根据另一个数字所求得的。
输入规格：
每个文件包含一个测试用例。每个用例占据一行包含了4个正整数：N1 N2 tag radix
这里N1和N2是一个不超过十位数字的正整数。其中每位数是小于它的进制的（比如十进制数中的每一位都是小于10的）并且是来自于集合{0-9，a-z}，其中0-9表示十进制数字0-9，a-z代表十进制数字10-35。最后一个数字“radix”，如果“tag”是1就是N1的进制，如果“tag”是2就是N2的进制。
输出规格：
对于每个测试用例，在一行内输出另一个数字的进制使得N1和N2是相等的。如果找不到使得N1和N2相等的进制的数那就输出“Impossible”。如果存在多个解决方法，那么输出尽可能小的进制。
样例输入:1
6 110 1 10
样例输出:1
2
样例输入:2
1 ab 1 2
样例输出:2
Impossible

分析与解题

昨天读题的时候发现题都没读懂，原因就是radix，这个单词在计算机中的意思是进制的意思。当明白了这个单词的意思，也就大致明白了题意。后来去百度搜索了，一堆人还依然翻译成基数，我就在想你到底有没有学过计算机。今天按照自己的想法去编码，第二次测试的时候已经达到23分。

C语言实现

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//最大数字20位 1开头
long long int result;
char n1[11];
char n2[11];
unsigned long long int tag;
unsigned long long int radix;
void input()
{
	scanf("%s%s", n1, n2);
	scanf("%d%d", &tag, &radix);
}
void calc()
{
	//first：找出谁是给出进制的，谁是要求的进制，
	//令c1是给出的进制，c2是要求得进制
	//为什么感觉这了这个有一种很奇异的感觉
	char c1[11], c2[11]; 
	if(tag == 1)
	{
		strcpy(c1, n1);
		strcpy(c2, n2);
	}
	else
	{
		strcpy(c1, n2);
		strcpy(c2, n1);
	}
	
	//下面所有带1的就是给出进制的数，2的就是要求进制的数	
	unsigned long long int t1 = 0; //令t1为给出进制的数
	unsigned long long int t2 = 0;
	int len1 = strlen(c1) - 1, len2 = strlen(c2) - 1;	
	//将给出进制的数转化为10进制并赋值给t1
	int i = len1;
	int j = 0;
	unsigned long long d = 1;
	while(i >= 0)
	{
		int tmp;
		if(c1[i] >= '0' && c1[i] <= '9')
		{
			//数字
			tmp = (int)(c1[i] - '0');
		}
		else
		{
			//字母
			tmp = (int)(c1[i] - 'a' + 10);
		}
		t1 += tmp * d;
		d *= radix;
		i--;
	}
	//come on，开始比较吧
	//1. 找到c2总最大的数字,之后从它加1开始计算
	i = 0;
	char max = 0;
	while(i <= len2)
	{
		if(max < c2[i])
			max = c2[i];
		i++;
	}
	//2. 开始从max开始计算
	if(max >= '0' && max <= '9')
		result = max - '0' + 1;
	else
		result = max - 'a' + 11;
	unsigned long long int low = result;
	unsigned long long int high = (t1 + 1) > result ? (t1 + 1) : result;
	result = (high + low) / 2;
	while(1)
	{
		i = len2;
		j = 0;
		unsigned long long d = 1;
		t2 = 0;
		while(i >= 0)
		{
			int tem;
			if(c2[i] >= '0' && c2[i] <= '9')
			{
				tem = (int)(c2[i] - '0');
			}
			else
			{
				tem = (int)(c2[i] - 'a' + 10);
			}
			t2 += tem * d;
			d *= result;
			if(t2 > t1)
				break;
			i--;
		}
		//second
		if(low > high)
		{
			result = -1;
			break;
		}
		if(t1 < t2)
		{
			high = result - 1;
			result = (high + low) / 2;
		}
		else if(t1 > t2)
		{
			low = result + 1;
			result = (high + low) / 2;	
		}
		else
			break;
	}
}
int main()
{
	input();
	calc();
	if(result == -1)
		puts("Impossible");
	else
		printf("%ld\n", result);
	return 0;
}

测试链接

click me