## 465 - Overflow

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 465 Overflow... Anyone could help me?

who are still thinking how to solve this problem, i got a tips to them..

Take input as string..
Check the length if it is grater then 10 then no need to convert it to number..
If the length is less then or equal to 10 then convert it to number.. and do required checking...
And the number type long double worked well for me..

--> sample input given by mf is very important..
try_try_try_try_&&&_try@try.com
This may be the address of success.

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

### 465 ! getting Wrong Ans.

Can anyone give me some critical cases for this problem?
can there be input like this: -000001234+ -200001 ?
both numbers will be non negative according to the problem statement...is it?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 465 ! getting Wrong Ans.

Search the board first. Don't create a new thread for a problem that already exists.
Check out the discussions here.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 465 - Overflow

take the input as string.
don't use big int(unless you use java),parse the numbers using sscanf and use LONG DOUBLE. then do what they say. be careful about input like A*0 A+-1 etc. thats all.

jakir052
New poster
Posts: 3
Joined: Sat Jun 26, 2010 11:27 am

### Re: 465 - Overflow

Try this without big int
Let a+b is to be tested
either a or b is too big, result is so.
but if neither are too big,the result can be big.
result will big if 2147483647-a<b holds
Same process apply on a*b
But be careful in case of either a or b is 0(zero)

RainCT
New poster
Posts: 2
Joined: Sat Apr 03, 2010 1:29 am

### Re: 465 - Overflow

I tried to do this "right" using strings but even though it works with all examples I've found on the web I always get WA. Can someone see what's wrong with my code?

(Note: I've given up on it and rewritten it to use double, but still it'd be nice to know why it failed).

Code: Select all

``````#include <iostream>
#include <string>
#include <sstream>

/* #include <climits> */
#define INT_MAX 2147483647

using namespace std;

template <class T>
string int2string(T number) {
stringstream stream;
stream << number;
return stream.str();
}

int string2int(string number) {
stringstream stream;
stream << number;
int inumber;
stream >> inumber;
return inumber;
}

bool bigger(string num, string ref) {
if (num.length() > ref.length())
return true;
if (num.length() < ref.length())
return false;
for (int i = 0; i < num.length(); ++i) {
if (num[i] > ref[i])
return true;
}
return false;
}

void lstrip(string& number) {
string::size_type pos = number.find_first_not_of("0", 0);
if (pos > 0)
number.erase(0, pos);
if (number == "")
number = "0";
}

int main() {
string max = int2string(INT_MAX);
string line;
while (getline(cin, line)) {
stringstream stream(line);
string num1, op, num2;
if (not (stream >> num1 >> op >> num2))
continue;
lstrip(num1);
lstrip(num2);
bool fail = false;
cout << line << endl;

if (bigger(num1, max)) {
cout << "first number too big" << endl;
fail = not (op[0] == '*' and num2 == "0");
}
if (bigger(num2, max)) {
cout << "second number too big" << endl;
fail = not (op[0] == '*' and num1 == "0");
}

if (not fail) {
if (op[0] == '+') {
unsigned int result = string2int(num1) + string2int(num2);
fail = bigger(int2string(result), max);
} else if (op[0] == '*' and num1 != "0" and num2 != "0") {
int n1 = string2int(num1);
int n2 = string2int(num2);
fail = ((n1 * n2) / n2) != n1;
}
}

if (fail) {
cout << "result too big" << endl;
}
}
}
``````

LionsHeart
New poster
Posts: 1
Joined: Tue Apr 12, 2011 10:48 am

### No.465 Overflow - RE

If i dont use string to get input and use sscanf to get each number and operator,
what method can i use?

I try the double type variales,but i found when the input is 99999999999999,
then the output will change into 10000000000000.

So,what can i do by using another way(Not the common way by get and sscanf)?

Thank you.

--------------EDIT-------------------

I try the other way without use sscanf
but i dont know why i get Runtime Error now.
Ca anyone help me to find the bug ?

Code:
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define FLUSH while(getchar()!='\n')
int main()
{
char ss[100],ss1[100];
double s1,s2,flag=INT_MAX;
char c;
while(scanf("%s %c %s",ss,&c,ss1)!=EOF){
FLUSH;
printf("%s %c %s\n",ss,c,ss1);
s1=atof(ss);
s2=atof(ss1);
if (s1>flag) printf("first number too big\n");
if (s2>flag) printf("second number too big\n");
switch(c)
{
case'+':
if(s1+s2>flag)
printf("result too big\n");
break;
case '*':
if(s1*s2>flag)
printf("result too big\n");
break;
}
}
return 0;
}

santosh
New poster
Posts: 2
Joined: Thu Apr 14, 2011 2:57 pm

### Re: 465 - Overflow

all my outputs matched with the test cases given above...but got wa..can anyone give me more test cases????

tiagoalex
New poster
Posts: 2
Joined: Thu Jan 05, 2012 1:43 am

I keep getting Runtime Error even when i have tried all the tests that ive found on the board and got the correct outputs.
I'm using double and before ive tried using Big Int and i was getting the same error. Can somebody help me and tell me what is wrong? The code seems good to me.

Code: Select all

``````import java.io.BufferedReader;
import java.io.IOException;

public class Main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String line[];
double a, b;
try {
while ((line = in.readLine().split(" ")) != null) {
a = Double.parseDouble(line[0]);
b = Double.parseDouble(line[2]);
System.out.println(line[0] + " " + line[1] + " " + line[2]);
if (a > (double) Integer.MAX_VALUE) {
System.out.println("first number too big");
}
if (b > (double) Integer.MAX_VALUE) {
System.out.println("second number too big");
}
if (line[1].equals("+")) {
if ((a + b) > (double) Integer.MAX_VALUE)
System.out.println("result too big");
} else if (line[1].equals("*")) {
if ((a * b) > (double) Integer.MAX_VALUE)
System.out.println("result too big");
}
}
} catch (IOException e) {
e.printStackTrace();
}
}

}
``````
EDIT: here is the code using Big Int, wich i got also RE.

Code: Select all

``````import java.io.BufferedReader;
import java.io.IOException;
import java.math.BigInteger;

public class Main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String line [];
BigInteger maxInt = new BigInteger(Integer.toString(Integer.MAX_VALUE));

try {
while((line = in.readLine().split(" ")) != null){
BigInteger intA = new BigInteger(line[0]);
BigInteger intB = new BigInteger(line[2]);
System.out.println(line[0]+" "+line[1]+" "+line[2]);
if(intA.compareTo(maxInt)==1){
System.out.println("first number too big");
}
if(intB.compareTo(maxInt)==1){
System.out.println("second number too big");
}
if(line[1].equals("+")){
System.out.println("result too big");
}
else if(line[1].equals("*")){
if((intA.multiply(intB)).compareTo(maxInt)==1)
System.out.println("result too big");
}
}
} catch (IOException e) {
e.printStackTrace();
}
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

I used BigInteger. You're getting a NullPointerException at the end of input. Check for in.readLine() == null before you pass it to split().
Check input and AC output for thousands of problems on uDebug!

asitmahato
New poster
Posts: 11
Joined: Mon Feb 20, 2012 11:04 am

It cab be solved with out using BigInt Class..
just use float number..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

http://uva.onlinejudge.org/index.php?op ... &Itemid=31
Check input and AC output for thousands of problems on uDebug!

i see
New poster
Posts: 9
Joined: Sat May 19, 2012 7:35 am

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
//#define LOCAL
#define fin cin
#define fout cout
using namespace std;
inline void multiply(const vector<int> &a, const vector<int> &b, vector<int> &result)
{

if ( a.back() == 0 || b.back() == 0) return ;
result.resize(a.size() + b.size() + 2,0);
int d, digit;
for (vector<int>::size_type i = 0; i < a.size(); ++i)
{
d = 0;
vector<int>::size_type j;
for (j = 0; j < b.size(); ++j)
{
digit = a.at(i) * b.at(j) + result.at(i+j) + d;
result.at(i+j) = digit % 10;
d = digit / 10;
}
if (d >= 1) result.at(i + j) += d;
}
vector<int>::size_type i = result.size();
while (i >= 1)
if (result.at(i - 1) != 0) break;
else {result.erase(result.begin() + i - 1); --i;}
}
inline void add(const vector<int> &a, const vector<int> &b, vector<int> &sum)
{
int d = 0, digit;
vector<int>::const_iterator a_it = a.begin(), b_it = b.begin();
while (a_it != a.end() && b_it != b.end())
{
digit = *a_it + *b_it +d;
sum.push_back(digit % 10);
d = digit / 10;
++a_it;
++b_it;
}
while (a_it != a.end())
{
digit = *a_it + d;
sum.push_back(digit % 10);
d = digit / 10;
++a_it;
}
while (b_it != b.end())
{
digit = *b_it + d;
sum.push_back(digit % 10);
d = digit /10;
++b_it;
}
if (d == 1) sum.push_back(d);
}
inline bool is_overflow(const vector<int> &m)
{
int array[11] = {7,4,6,3,8,4,7,4,1,2};
vector<int> max_int( array, array + 10);
if (m.size() > max_int.size()) return true;
else if (m.size() < max_int.size()) return false;
else for (vector<int>::size_type i = m.size(); i >= 1; --i)
if (m.at(i) > max_int.at(i)) return true;
else if (m.at(i) < max_int.at(i)) return false;
return false;
}
int main()
{
#ifdef LOCAL
ifstream fin("in.cpp");
ofstream fout("out.cpp");
#endif
string s1, s2;
vector<int> a, b, result;
char mark;
while (fin >> s1 >> mark >> s2)
{
fout << s1 << " " << mark << " " << s2 << endl;
a.clear();
for (string::size_type i = s1.size(); i >= 1; --i)
a.push_back(s1.at(i - 1) - '0');
b.clear();
for (string::size_type i = s2.size(); i >= 1; --i)
b.push_back(s2.at(i - 1) - '0');
if (mark == '*') {
multiply( a, b, result);
if (is_overflow(a)) fout << "first number too big" << endl;
if (is_overflow(b)) fout << "second number too big" << endl;
if (is_overflow(result)) fout << "result too big" << endl;
} else {
if (is_overflow(a)) fout << "first number too big" << endl;
if (is_overflow(b)) fout << "second number too big" << endl;
if (is_overflow(result)) fout << "result too big" << endl;
}
result.clear();
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA