d873: 00465 - Overflow
Tags: big-handle
出處:https://zerojudge.tw/ShowProblem?problemid=d873
提交:https://zerojudge.tw/Submissions?problemid=d873&account=allllllan123456
問題:給你一個非負整數 $x$、二元運算子 $f\in\{+, *\}$,以及另一個非負整數 $y$,問你 $x$、$y$、$f(x,y)$ 三者是否分別會超出 int 的範圍?
解法:這題看似要先用大數方法算出答案再來判斷,其實不然。要判斷一個非負整數 (無前導零) 是否超出 int,可以利用字串長度與內建字串比較機制來進行,超出 10 位數者一定超出 int,剛好與 int 上界 (2147483647) 同位數者可由高位數到低位數依序比較,小於 10 位數者一定不超出 int。在運算的部分,一個運算元為零就保證結果為零;一個運算元超出 int 但另一個運算元不為零就會讓結果也超出 int;兩個運算元都不超出 int 也不為零的話,可以保證運算結果在 long long 內,於是判斷也不會出錯。
1#include <bits/stdc++.h>
2using namespace std;
3
4string str[2], op;
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
7 while (cin >> str[0] >> op >> str[1]) {
8 cout << str[0] << ' ' << op << ' ' << str[1] << '\n';
9 bool first = false, second = false;
10 if (str[0].length()>10 ||
11 str[0].length()==10 && str[0]>to_string(INT_MAX))
12 first=true, cout << "first number too big\n";
13 if (str[1].length()>10 ||
14 str[1].length()==10 && str[1]>to_string(INT_MAX))
15 second=true, cout << "second number too big\n";
16 if (op[0]=='*' && (str[0]=="0"||str[1]=="0")) {}
17 else if (first || second) cout << "result too big\n";
18 else {
19 long long a = stoi(str[0]), b = stoi(str[1]);
20 if (op[0]=='+' && a+b>INT_MAX ||
21 op[0]=='*' && a*b>INT_MAX)
22 cout << "result too big\n";
23 }
24 }
25 return 0;
26}