465 - Overflow

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

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

Post by Obaida » Sat Jul 11, 2009 4:25 am

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.. :)
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.

Post by regan » Wed May 26, 2010 12:45 am

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?

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

Re: 465 ! getting Wrong Ans.

Post by sohel » Wed May 26, 2010 11:30 am

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 465 - Overflow

Post by Shafaet_du » Sat Sep 04, 2010 9:08 pm

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

Post by jakir052 » Fri Sep 10, 2010 10:12 pm

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

Post by RainCT » Tue Mar 01, 2011 8:36 pm

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

Post by LionsHeart » Tue Apr 12, 2011 10:56 am

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;
}

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

Re: 465 - Overflow

Post by santosh » Wed Jun 15, 2011 3:21 pm

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

465 - Overflow why? RE (Java) please help

Post by tiagoalex » Wed Jan 11, 2012 7:12 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.
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();
		}
	}

}

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

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

Post by brianfry713 » Thu Jan 19, 2012 1:37 am

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

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

Post by asitmahato » Mon Feb 20, 2012 11:37 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

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

Post by brianfry713 » Fri Feb 24, 2012 9:23 pm

junyiguoji, you're not giving us enough information to help you.
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

465, please help me , thanks !

Post by i see » Wed Aug 01, 2012 3:32 pm

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;
}

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

Re: 465, please help me , thanks !

Post by brianfry713 » Wed Aug 01, 2012 10:00 pm

2000000000 + 2000000000
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

Re: 465, please help me , thanks !

Post by i see » Thu Aug 02, 2012 7:13 am

Hi brianfry713 ,thank you ! With your helps it's AC.

Post Reply

Return to “Volume 4 (400-499)”