1065. A+B and C (64bit) (20)

http://www.patest.cn/contests/pat-a-practise/1065

---

 

原题如下

Given three integers A, B and C in [-2⁶³, 2⁶³], you are supposed to tell whether A+B > C.
Input Specification:
The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
Output Specification:
For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).
Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

---

 
分析，其实就是自己做加减法进位的问题，需要考虑正负号的细节。
正负数加减法的规则可以参考百度文库，一大堆小学生教材，哈哈~
大概是这样，比较两个数a和b：

• 最终结果符号的判定：如果|a|>=|b|那么结果的符号与a相同，反之符号与b相同；
• 数值计算，不管正负号，用绝对值大的那个做操作数1，绝对值小的做操作数2，如果a，b同号做操作数1+操作数2，异号做操作数1–操作数2；

---

 
我的代码（好久没写c++，各种复杂，见谅）
其中isBiggerAbs是判断a与b的绝对值大小的，isBigger是判断实际值大小的，swapss是交换元素。
另外0x30是字符’0’的ASCII码来着~输入的时候是按照字符流看待的，计算的时候转换成了数字，然后比较的时候为了和c比方便又转换回去了。
另外给的Sample Input里面那个一长串的就是上限和下限了，加上符号20位足够放。

#include <iostream>
#include <string.h>
using namespace std;
void swapss(char*a, char* b)
{
	char t[20];
	strcpy(t, a);
	strcpy(a, b);
	strcpy(b, t);
}
bool isBiggerAbs(char* a, char* b)
{
	int len_a, len_b;
	len_a = strlen(a);
	len_b = strlen(b);
	if (len_a > len_b)
		return true;
	else if (len_a < len_b)
		return false;
	//只需比较位数一样的
	for (int i = 0; i < len_a; i++)
	{
		if (a[i] > b[i])
			return true;
		else if (a[i] < b[i])
			return false;
	}
	//完全相等
	return false;
}
bool isBigger(char* a, char* b)
{
	//Judge if a > b
	bool neg_a = (a[0] == '-');
	bool neg_b = (b[0] == '-');
	if (neg_a && !neg_b)
		return false;
	else if (!neg_a && neg_b)
		return true;
	if (!neg_a)
		return isBiggerAbs(a, b);
	else
	{
		a = strtok(a, "-");
		b = strtok(b, "-");
		return !isBiggerAbs(a, b);
	}
}
void bigPlus(char* a, char* b, char* r)
{
	// c = a + b
	int len_a, len_b;
	bool isNeg_a = false;
	bool isNeg_b = false;
	bool isNeg_r = false;
	if (a[0] == '-')
	{
		char* pch = strtok(a, "-");
		a = pch;
		isNeg_a = true;
	}
	if (b[0] == '-')
	{
		char* pch = strtok(b, "-");
		b = pch;
		isNeg_b = true;
	}
	if (!isBiggerAbs(a, b))
	{
		//Swap a and b
		swapss(a, b);
		isNeg_r = isNeg_b;
	}
	else
		isNeg_r = isNeg_a;
	if (isNeg_a)
	{
		bool t = isNeg_a;
		isNeg_a = isNeg_b;
		isNeg_b = t;
	}
	len_a = strlen(a);
	len_b = strlen(b);
	int index_a = len_a - 1;
	int index_b = len_b - 1;
	int remainder = 0;
	int count = 0;
	while (index_a >= 0 || index_b >= 0)
	{
		int op0 = 0;
		if (index_a >=0 )
			op0 = (int)a[index_a] - 0x30;
		if (isNeg_a)
			op0 = -op0;
		int op1 = 0;
		if (index_b >= 0)
			op1 = (int)b[index_b] - 0x30;
		if (isNeg_b)
			op1 = -op1;
		int result = op0 + op1 + remainder;
		if (result < 0)
		{
			remainder = -1; //negative raminder (<'0')
			result += 10;
		}
		else if (result > 9)
		{
			remainder = 1; //positive remainder (>'9')
			result -= 10;
		}
		else
			remainder = 0;
		r[count++] = (char)(result + 0x30);
		index_a--;
		index_b--;
	}
	//Deal with the last remainder
	if (remainder > 0)
	{
		r[count++] = (char)(remainder+0x30);
	}
	else if (remainder < 0)
	{
		r[count++] = (char)(remainder + 0x30);
	}
	if (isNeg_r)
		r[count++] = '-';
	char temp[21];
	int t = 0;
	while ((--count) >= 0)
	{
		temp[t++] = r[count];
	}
	temp[t] = '\0';
	strcpy(r, temp);
}
int main()
{
	//Read huge integer as charset
	int T; //Nubmer of test cases
	cin >> T;
	char a[20];
	char b[20];
	char c[20];
	char result[21];
	for (int i = 0; i < T; i++)
	{
		//Deal with test cases
		cin >> a >> b >> c;
		bigPlus(a, b, result);
		bool is_bigger = isBigger(result, c);
		cout << "Case #" << i + 1 << ": ";
		if (is_bigger)
			cout << "true";
		else
			cout << "false";
		if (i < T - 1)
			cout << endl;
	}
	return 0;
}

 

---

结果

评测结果

时间	结果	得分	题目	语言	用时(ms)	内存(kB)	用户
2月22日 20:46	答案正确	20	1065	C++ (g++ 4.7.2)	1	360

测试点

测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	1	360	12/12
1	答案正确	1	360	4/4
2	答案正确	1	360	4/4