当前位置：首页 > news >正文

UVa 465 Overflow

news 2026/6/13 3:00:10

题目描述

题目要求判断表达式中的两个非负整数以及运算结果是否超出323232位有符号整数的表示范围（即[−231,231−1][-2^{31}, 2^{31}-1][−231,231−1]，但题目中整数为非负，因此范围为[0,231−1][0, 2^{31}-1][0,231−1]）。表达式格式为整数运算符整数，运算符为+或*。对于每个表达式，输出原始输入行，然后根据情况输出first number too big、second number too big、result too big中的若干行。

输入格式

输入包含多行，每行一个表达式，格式如300 + 3或99999999999999999999 + 11。整数可能非常大（超过646464位范围）。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个表达式，先输出原始输入行，然后输出相应的错误信息（最多三行）。信息按顺序输出：先判断第一个数，再判断第二个数，最后判断结果。

样例

输入

300 + 3 99999999999999999999 + 11

输出

300 + 3 99999999999999999999 + 11 first number too big result too big

题目分析

本题的核心是判断大整数是否超出231−1=21474836472^{31}-1 = 2147483647231−1=2147483647的范围。

判断数字是否太大

由于输入整数可能非常大（超过646464位），不能直接转换为内置整数类型。可以通过字符串长度和前缀判断：

若字符串长度>10> 10>10，则一定超过214748364721474836472147483647（因为214748364721474836472147483647是101010位数）。
若长度为101010，则比较字符串与"2147483647"的字典序（因为数字无前导零，可直接比较字符串）。
若长度≤9\le 9≤9，则转换为整数后与214748364721474836472147483647比较。

注意：输入数字可能有前导零，需要先去除。

加法结果判断

两个正整数相加的结果可能超出323232位范围。由于数字可能很大，不能直接计算，可以通过字符串模拟加法或利用长度判断：

若两个数的长度都≤10\le 10≤10，可转换为整数直接计算后比较。
否则，结果长度至少为max⁡(len1,len2)\max(len1, len2)max(len1,len2)或max⁡(len1,len2)+1\max(len1, len2)+1max(len1,len2)+1。若结果长度>10> 10>10，则一定太大；若长度为101010，需比较具体值。

乘法结果判断

两个正整数相乘的结果可能非常大。可以这样判断：

若任一数为000，结果为000，不会太大。
若两个数的长度之和≥12\ge 12≥12，则乘积至少为101110^{11}1011，远超2312^{31}231，可直接判定为太大。
否则，转换为整数后计算乘积并与214748364721474836472147483647比较。

实现方法

参考代码中使用了字符串模拟加法和减法（虽然本题只有加法，但代码也处理了减法），并提供了is_too_big函数判断字符串是否超出最大值。

复杂度分析

每个表达式处理O(L)O(L)O(L)时间，LLL为数字字符串长度，可接受。

代码实现

// Overflow// UVa ID: 465// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;boolis_too_big(string number,longlongmax_value){if(number.length()>10||(number.length()==10&&number.front()>'2'))returntrue;else{longlongnumber_value=stoll(number);if(number_value>max_value)returntrue;}returnfalse;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line,first,middle,second;while(getline(cin,line)){istringstreamiss(line);iss>>first>>middle>>second;assert(middle=="*"||middle=="+"||middle=="-");cout<<line<<'\n';intmaxLength=max(first.length(),second.length());while(first.front()=='0'&&first.length()>1)first.erase(first.begin());while(second.front()=='0'&&second.length()>1)second.erase(second.begin());if(is_too_big(first,numeric_limits<int>::max()))cout<<"first number too big\n";if(is_too_big(second,numeric_limits<int>::max()))cout<<"second number too big\n";// beware of that one of numbers is zeroif(middle=="*"){if(first=="0"||second=="0")continue;if(first.length()+second.length()>=12){cout<<"result too big\n";}else{longlongfirst_value=stoll(first),second_value=stoll(second);longlongresult_value=first_value*second_value;if(result_value>numeric_limits<int>::max())cout<<"result too big\n";}continue;}intsign=1;stringresult(maxLength+1,'0');while(first.length()<result.length())first.insert(first.begin(),'0');while(second.length()<result.length())second.insert(second.begin(),'0');reverse(first.begin(),first.end());reverse(second.begin(),second.end());if(middle=="+"){intsum=0,carry=0;for(inti=0;i<result.length();i++){sum=first[i]-'0'+second[i]-'0'+carry;result[i]=sum%10+'0';carry=sum/10;}}else{for(inti=first.length()-1;i>=0;i--)if(second[i]>first[i]){sign=-1;swap(first,second);break;}intsum=0,borrow=0;for(inti=0;i<result.length();i++){sum=first[i]-'0'-second[i]-'0'-borrow;if(sum<0){sum+=10;borrow=1;}else{borrow=0;}result[i]=sum+'0';}}reverse(result.begin(),result.end());while(result.front()=='0'&&result.length()>1)result.erase(result.begin());if(sign>0){if(is_too_big(result,numeric_limits<int>::max()))cout<<"result too big\n";}else{if(is_too_big(result,(longlong)numeric_limits<int>::max()+1))cout<<"result too big\n";}}return0;}