## 465 - Overflow

Moderator: Board moderators

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### thank you

hi, soyoja!! Your sample output really helped me out.
I use 16 bit compiler running under DOS, had a hard time working on this problem since the judge is using 32 bit compiler

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
You're welcome~ ^^;

In this problem, I believe that enough test case make accepted solution.

( Datatype boundary limits are so critical... ^^ )

Joybo
New poster
Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

### [465]I got wa!

[c]
#include <stdio.h>
#include <string.h>

#define INT_MAX 2147483647

void main(void){
long double n1,n2;
char ch[4];

while(scanf("%lf",&n1)==1){
scanf("%s%lf",&ch,&n2);
if(n1>INT_MAX||n2>INT_MAX){
if(n1>INT_MAX) printf("first number too big\n");
if(n2>INT_MAX) printf("second number too big\n");
if(!n1&&!n2) printf("result too big\n");
}else{
if(strcmp(ch,"+")==0&&n1+n2>INT_MAX) printf("result too big\n");
if(strcmp(ch,"*")==0&&n1*n2>INT_MAX) printf("result too big\n");
}
}
}
[/c]

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
if(!n1&&!n2) printf("result too big\n");
This means if n1 and n2=0, then the result will be too big???
0+0 = 0
0*0 = 0
??????

And the integers will be arbitrarily long, so I dont kknow if long double can handle these kind of integers (there could be precision errors). If long double doesn't work, try treating the integers as arrays of integers.
Good luck!!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

gawi
New poster
Posts: 3
Joined: Sun Jul 13, 2003 10:19 am
Location: Taiwan

### problem 465 why wa ?

Following is my code.
I debug again and again.
plz help me , thanx

[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

#define BUF_SIZE 10000

int overflow(char *num) {
const static char *max_int="2147483647";
const static int max_len=10;
int len;

while((*num)=='0') num++;
if((*num)=='\0') num--;

len=strlen(num);
if(len>max_len) {
return 1;
}
if(len==max_len && strcmp(num,max_int)>0) {
return 1;
}
return 0;
}

int main() {
char buf[BUF_SIZE],str1[BUF_SIZE],str2[BUF_SIZE],opr[2];
int num1,num2; /* when overflow, \$num=-1 */
while(fgets(buf,sizeof(buf),stdin)!=NULL) {
printf("%s",buf);
sscanf(buf,"%s %s %s",str1,opr,str2);
if(overflow(str1)) {
num1=-1;
printf("first number too big\n");
} else
num1=atoi(str1);
if(overflow(str2)) {
num2=-1;
printf("second number too big\n");
} else
num2=atoi(str2);

if(opr[0]=='+') {
if(num1<0 || num2<0)
printf("result too big\n");
else {
if(INT_MAX-num1<num2)
printf("result too big\n");
}
} else if(opr[0]=='*') {
if(num1*num2!=0) { /* Neither num1 and num2 is zero */
if(num1<0 || num2<0)
printf("result too big\n");
else {
if(INT_MAX/num1<num2)
printf("result too big\n");
}
}
}
}
return 0;
}
[/c]

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
hi... i got WA 3 times for this problem... i wonder where's my fault...

here is the sample input i use to work with :

Code: Select all

``````2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
350 +      20
0000350     +    00020
``````
and the sample output is :

Code: Select all

``````2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
result too big
2147483648 * 0
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
350 +      20
0000350     +    00020
``````
is there any thing wrong ? or there is another tricky input ?
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
hi... i got WA 3 times for this problem... i wonder where's my fault...

here is the sample input i use to work with :

Code: Select all

``````2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
350 +      20
0000350     +    00020
``````
and the sample output is :

Code: Select all

``````2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
result too big
2147483648 * 0
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
350 +      20
0000350     +    00020
``````
is there any thing wrong ? or there is another tricky input ? thanx before
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Hi Shaka,

Yours output looks ok... But I had a mistake like this
000000000035 + 000000000035
first number too big
second number too big

But it was wrong! Just get rid of leading zeroes.

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
i've found my mistake and i've got AC...

this is my input :

Code: Select all

``````2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2147483648 * 1
2147483648 + 0
2147483648 * 1
2000000000 + 2000000000
1000000 * 1000000
0 * 0
0 + 0
2147483647 * 2147483647
2147483647 + 2147483647
0000000000000000350 + 20
350 +      20
0000350     +    00020
2147483647*2147483647
2147483647+2147483647
1000000*1000000
1000000+1000000
5*2
6+7
0000000000000000000000034+0000000000000000000002
0000000000000000000000034*0000000000000000000002
``````

and this is my output :

Code: Select all

``````2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
2147483648 * 0
first number too big
2147483648 * 1
first number too big
result too big
2147483648 + 0
first number too big
result too big
2147483648 * 1
first number too big
result too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
0 * 0
0 + 0
2147483647 * 2147483647
result too big
2147483647 + 2147483647
result too big
0000000000000000350 + 20
350 +      20
0000350     +    00020
2147483647*2147483647
result too big
2147483647+2147483647
result too big
1000000*1000000
result too big
1000000+1000000
5*2
6+7
0000000000000000000000034+0000000000000000000002
0000000000000000000000034*0000000000000000000002
``````
thanx for the correction....
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:
There is an input for which most of the people get WA ! I have corrected many person's code by giving this input. I am giving it here, if any body need more help, then write here, in future i will help again.
2147483648 + -1
Yes, it is possible . Just try it with your code. First number is too big but result is not. Hopefully many of u can get accepted now.

Niaz
The Last Man Standing

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
u can chake this input

input
2147483648 + -1

output
2147483648 + -1
first number too big

prince

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### The math way.

Greetings!.
Maxim wrote:I've solved it without BigInt.

Maxim
People, try to re-think the problem without the use of BigNums.
It is WAY easier.
Ah!, and a tip, the input lines won't exceed 255 chars
Keep posting!.
_.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
My code gives correct answers for every input posted here... Still WA with the judge... Any sugestions???
[cpp]#include <iostream>
#include <sstream>
#include <string>
using namespace std;

string s1, s2, ss;
char op;
long long n1, n2;
bool f, s, r;

int main(){
while(getline(cin, ss)){
long p = 0;

while(ss[p] == ' ') p++;
while(ss[p] == '0') p++;
if(ss[p] < '0' || ss[p] > '9') p--;

s1 = "";

while(ss[p] >= '0' && ss[p] <= '9')
s1 = s1 + ss[p++];

while(ss[p] == ' ')p++;

op = ss[p++];

while(ss[p] == ' ')p++;
while(ss[p] == '0') p++;
if(ss[p] < '0' || ss[p] > '9') p--;

s2 = "";

while(ss[p] >= '0' && ss[p] <= '9')
s2 = s2 + ss[p++];

f = s = r = false;
n1 = n2 = 1;
if(s1.size() > 15){
f = true;
}else{
istringstream sin(s1);
sin >> n1;
if(n1 > 0x7FFFFFFF) f = true;
}

if(s2.size() > 15){
s = true;
}else{
istringstream sin(s2);
sin >> n2;
if(n2 > 0x7FFFFFFF) s = true;
}

if(!f && !s){
if(op == '*' && n1 * n2 > 0x7FFFFFFF) r = true;
if(op == '+' && n1 + n2 > 0x7FFFFFFF) r = true;
}
r = r || f || s;

if((n1 == 0 || n2 == 0) && op == '*') r = false;

cout << ss << endl;
if(f) cout << "first number too big\n";
if(s) cout << "second number too big\n";
if(r) cout << "result too big\n";

}

return 0;
}
[/cpp]

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
mohiul alam prince wrote:u can chake this input

input
2147483648 + -1

output
2147483648 + -1
first number too big

prince
According to problem statement "an expression consisting of two non-negative integer". Is problem description wrong????

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
``````Code Removed