Page 6 of 7

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

Posted: Sat Jul 11, 2009 4:25 am
by Obaida
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.. :wink:

--> sample input given by mf is very important.. :)

465 ! getting Wrong Ans.

Posted: Wed May 26, 2010 12:45 am
by regan
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?

Re: 465 ! getting Wrong Ans.

Posted: Wed May 26, 2010 11:30 am
by sohel
Search the board first. Don't create a new thread for a problem that already exists.
Check out the discussions here.

Re: 465 - Overflow

Posted: Sat Sep 04, 2010 9:08 pm
by Shafaet_du
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.

Re: 465 - Overflow

Posted: Fri Sep 10, 2010 10:12 pm
by jakir052
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)

Re: 465 - Overflow

Posted: Tue Mar 01, 2011 8:36 pm
by RainCT
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;
		}
	}
}

No.465 Overflow - RE

Posted: Tue Apr 12, 2011 10:56 am
by LionsHeart
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)?

Please teach me
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;
}

Re: 465 - Overflow

Posted: Wed Jun 15, 2011 3:21 pm
by santosh
all my outputs matched with the test cases given above...but got wa..can anyone give me more test cases????

465 - Overflow why? RE (Java) please help

Posted: Wed Jan 11, 2012 7:12 am
by tiagoalex
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.
Thank you in advance!!

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		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.io.InputStreamReader;
import java.math.BigInteger;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		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("+")){
					if((intA.add(intB)).compareTo(maxInt)==1)
						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();
		}
	}

}

Re: 465 - Overflow why? RE (Java) please help

Posted: Thu Jan 19, 2012 1:37 am
by brianfry713
I used BigInteger. You're getting a NullPointerException at the end of input. Check for in.readLine() == null before you pass it to split().

Re: 465 - Overflow why? RE (Java) please help

Posted: Mon Feb 20, 2012 11:37 am
by asitmahato
It cab be solved with out using BigInt Class..
just use float number..

Re: 465 - Overflow why? RE (Java) please help

Posted: Fri Feb 24, 2012 9:23 pm
by brianfry713
junyiguoji, you're not giving us enough information to help you.
http://uva.onlinejudge.org/index.php?op ... &Itemid=31

465, please help me , thanks !

Posted: Wed Aug 01, 2012 3:32 pm
by i see
I try my best to find any faults in my cides, it's always RE, please help me, thans in advace !
#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 {
add( 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;
}
result.clear();
}
return 0;
}

Re: 465, please help me , thanks !

Posted: Wed Aug 01, 2012 10:00 pm
by brianfry713
2000000000 + 2000000000

Re: 465, please help me , thanks !

Posted: Thu Aug 02, 2012 7:13 am
by i see
Hi brianfry713 ,thank you ! With your helps it's AC.