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

時間限制?100 ms 內存限制?65536 kB 代碼長度限制?16000 B 判題程序?Standard 作者?HOU, Qiming

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>c 是否成立的問題，唯一的坑點就是范圍上線是 2^63 超過了計算機 long long 或 ?__int64 的上限( 2^63-1 )。所以無論在輸入方面和計算方面都產生了一些障礙。 本弱的基礎思想是用字符串讀入所有數據，然后判斷是否上溢出（這里指的是 long long 的上溢出，下文中亦如此），如果上溢出則進行特殊處理，否則正常處理。下面略具體的說下思路：（思路有可能會顯得有些亂，但是絕對正確） 首先如果 a 和 b 都沒有上溢出，那么求 a+b。如果上溢出必然 true，如果是下溢出必然 false，如果沒有溢出則判斷 c 是否上溢出，如果 c 上溢出則必然 false，否則正常比較處理即可。 如果 a 和 b 中有一個出現了上溢出，首先將上溢出的那一項挪至 a，方便后續處理。然后判斷 c 是否上溢出，如果 c 上溢出則通過 b 的符號即可知 a+b>c 是否成立。如果 c 沒有上溢出則通過 a*b 的符號判斷，如果異號必然 a+b<=c，否則計算下 a+b 即可（具體小技巧看程序）。 另：本弱處理的不是特別優美，導致我需要單獨特殊處理下 a 和 b 都是 -2^63 的情況。 特別注意！！！！！！！！！！！！！ 網上很多很多的解題報告都是錯的！！！！錯在 2^63 + 2^63 > 1 這組數據上，然而該題的官方數據中沒有此類數據，導致許多錯誤的程序都可以通過。 提供一組數據：

8
1 2 3
2 3 4
10 -10 0
101 -100 0
9223372036854775807 -9223372036854775808 0
9223372036854775808 9223372036854775808 1
9223372036854775808 -9223372036854775808 1
-9223372036854775808 -9223372036854775808 -1

ans:

Case #1: false
Case #2: true
Case #3: false
Case #4: true
Case #5: false
Case #6: true
Case #7: false
Case #8: false

?

代碼：

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 0x7FFFFFFFFFFFFFFF; 5 const int MAXN = 30; 6 const char str[MAXN] = "9223372036854775808"; 7 const char st[MAXN] = "-9223372036854775808"; 8 9 char a[MAXN], b[MAXN], c[MAXN]; 10 LL na, nb, nc, nd; 11 12 int check( LL x ) { return x > 0 ? 1 : x < 0 ? -1 : 0; } 13 14 int main() { 15 int t, cnt = 0; 16 int ta, tb, tc, td; 17 bool fa, fb, fc; 18 scanf( "%d", &t ); 19 while( t-- ) { 20 printf( "Case #%d: ", ++cnt ); 21 scanf( "%s%s%s", a, b, c ); 22 if( !strcmp( a, st ) && !strcmp( b, st ) ) { 23 puts( "false" ); continue; 24 } 25 fa = !strcmp( a, str ); 26 fb = !strcmp( b, str ); 27 fc = !strcmp( c, str ); 28 if( !fa && !fb ) { 29 sscanf( a, "%I64d", &na ); ta = check( na ); 30 sscanf( b, "%I64d", &nb ); tb = check( nb ); 31 if( !fc ) { sscanf( c, "%I64d", &nc ); tc = check( nc ); } 32 nd = na + nb; td = check( nd ); 33 if( ( ta * tb ) > 0 && ( ta * td ) < 0 ) { 34 if( ta > 0 ) puts( "true" ); 35 else puts( "false" ); 36 } else { 37 if( fc ) puts( "false" ); 38 else puts( nd > nc ? "true" : "false" ); 39 } 40 } else { 41 ta = a[0] == '-' ? -1 : a[0] == '0' ? 0 : 1; 42 tb = b[0] == '-' ? -1 : b[0] == '0' ? 0 : 1; 43 if( fc ) { 44 if( !fa ) { swap( a, b ); swap( ta, tb ); swap( fa, fb ); } 45 if( tb <= 0 ) puts( "false" ); 46 else puts( "true" ); 47 } else { 48 sscanf( c, "%I64d", &nc ); tc = check( nc ); 49 if( ta ^ tb ) { 50 if( !fa ) { swap( a, b ); swap( ta, tb ); swap( fa, fb ); } 51 sscanf( b, "%I64d", &nb ); 52 nd = INF + nb + 1; 53 puts( nd > nc ? "true" : "false" ); 54 } else puts( "true" ); 55 } 56 } 57 } 58 return 0; 59 } View Code

?

轉載于:https://www.cnblogs.com/Hitman_47/p/5185649.html

總結

以上是生活随笔為你收集整理的PAT 1065 A+B and C (64bit) (20)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。