PAT甲级 1065 A+B and C (64bit) (20 分)

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

Given three integers A, B and C in (−263,263), 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

Thanks to Jiwen Lin for amending the test data.

题意

给出三个整数A,B,C，如果A+B>C，则输出true；否则，输出false

思路1

由于long long的范围是[-2^63,2^63),因此题目中给出的两个整数相加有可能会出现溢出（正溢出或负溢出）所谓溢出即两个正数之和等于负数或者两个负数之和等于正数，所以直接进行大小判断会造成错误。要分别处理两种溢出的情况

1.正溢出情况，当A+B>2^63 ，A + B > C 必然成立 但是A+B超出long long的正向最大值而溢出，由题目可知 A 和 B最大均为 2^63 - 1, 故A+B最大为2^64 - 2, 因此使用long long 存储正溢出后的区间为[-2^63, -2]，即当A>0,B>0,A+B<0时输出true

2.负溢出情况，同理正溢出情况 使用long long 存负溢出后的区间为[0, 2^63),即当A<0,B<0,A+B>=0时输出false

3.没有溢出时正常输出

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include 
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		long long int a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);//用cin最后一个测试点会错误
		long long res = a + b;  //必须先存放到long long 中再与c比较否则后两组数据会错误
		bool flag;
		if (a > 0 && b > 0 && res < 0)	flag = true;//正溢出为true
		else if (a < 0 && b < 0 && res >= 0)	flag = false;//负溢出为false
		else if (res > c)	flag = true;	//无溢出时 a + b > c 为true
		else if (res <= c)	flag = false;	//无溢出时 a + b <= c 为false
		if (flag == true)
			cout << "Case #" << i << ": true" << endl;
		else if(flag == false)
			cout << "Case #" << i << ": false" << endl;
	}
	return 0;
}

思路2 使用long doule可以精确到20位

AC代码

#include 
using namespace std;

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		long double a, b, c;//long doubel能精确到20位
		cin >> a >> b >> c;
		if (a + b > c)
			cout << "Case #" << i << ": true" << endl;
		else 
			cout << "Case #" << i << ": false" << endl;
	}
	return 0;
}