## 465 - Overflow

Moderator: Board moderators

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I did not find any special trick when I solved it, I just used some regular PASCAL functions like val and then checked the conditions, if you want a larger explanation, send me a private message or keep posting here if you want to, hope this helps,

Yandry.

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Can YOu Give Me Some Test Data???
I Think This Wiill Help Me.

Rocky

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Rocky,

Nevertheless, here is some test data for you and
for anyone who might need it.

I am not sure about several things.

1) Does the input contain negative numbers ? - I guess not

2) Does the input always contain SPACEs between the numbers
and the operation sign ( plus + ot multiply * ) - Well, I guess it
always contains such SPACEs but ... To be on the safe side consider
the opposite option too.

3) Does the input contain numbers in which leading zeros are
present ? I hope not but ... Again, who knows.

INPUT

Code: Select all

``````300 + 3
9999999999999999999999 + 11
2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0
2000000000 + 2000000000
1000000 * 1000000
2147483648 * -1
-1 * 2147483648
2147483647 * 2147483647
32768 * -65536
0123232323232 * 2222222222222
000012 * 2222222222222
10000000000*10000
1002*10000``````

OUTPUT

Code: Select all

``````300 + 3
9999999999999999999999 + 11
first number too big
result too big
2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
2147483648 * 0
first number too big
2000000000 + 2000000000
result too big
1000000 * 1000000
result too big
2147483648 * -1
first number too big
-1 * 2147483648
second number too big
2147483647 * 2147483647
result too big
32768 * -65536
0123232323232 * 2222222222222
first number too big
second number too big
result too big
000012 * 2222222222222
second number too big
result too big
10000000000*10000
first number too big
result too big
1002*10000``````

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### Thank's For Help

Thank's
I Think It Help Me....

Rocky

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
The input is bad, no negative Integer is allowed.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
my critical in/out was

Code: Select all

``000000000000000000000000000000000000000000000000000000000000000000000009999999999999999999999999999999999999999999999999999999999 + 1``
Regards
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
There isn't any input like 123*5 or 123 *5 and so on

I did it like this

Code: Select all

``````while(gets(line))
{
if(!strlen(line)){printf("\n");continue;}
printf("%s\n",line);
sscanf(line,"%s %c %s",&a,&sign,&b);
...``````
keep it real!

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

### 465 need a hand filled by help

please help me.I m undone.I dont know what r the other tricks?I hv done what i can do.The last step is posting my code to u.

//Code deleted after AC
Last edited by tuman on Sat Oct 29, 2005 2:58 pm, edited 2 times in total.
We the dreamer of the dreamy dream...

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Think of cases where digits in the input number are greater than 15. e.g.

Code: Select all

``````564651354687965135846587984354861384 + 332132132132132154684768465413654654684
``````
You may consider storing the given number as a string.
Where's the "Any" key?

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:
thnx solaries ,anyway i hv done this.
Yes i should hv taken input as string.Though this prog does not need big integer.Any way thanx once again. But i would also like to thank Tanvir (Aatel) for notifying me this problem.
We the dreamer of the dreamy dream...

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm

### wtf?????

I have used all the test data in the forum but I still get wrong answer; here is my program.

#include<iostream>
#include<functional>
#include<algorithm>
#include<iterator>
#include<string>
#include<sstream>
#include<climits>
#include<cassert>
using namespace std;
#define LIM 2147483647
int main()
{
long long n1,n2,n3;
string s,t;
char c;
while(getline(cin,t)){
cout<<t<<endl;
istringstream in(t);
in>>n1>>c>>n2;
if(n1>LIM)
cout<<"first number too big"<<endl;
if(n2>LIM)
cout<<"second number too big"<<endl;
if(c=='+'){
n3=n1+n2;
if(n3>LIM)
cout<<"result too big"<<endl;
}
if(c=='*'){
n3=n1*n2;
if(n3>LIM)
cout<<"result too big"<<endl;
}
}
}

I am using LIM to disregard any ambiguity about whether to use INT_MAX or LONG_MAX (defined int climits)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try this input:

Code: Select all

``````999999999999999999999999999999 * 999999999999999999999999999999
4294967296 * 4294967296
4294967295 * 4294967295
999999999999999999999999999999 * 0
``````
Correct output:

Code: Select all

``````999999999999999999999999999999 * 999999999999999999999999999999
first number too big
second number too big
result too big
4294967296 * 4294967296
first number too big
second number too big
result too big
4294967295 * 4294967295
first number too big
second number too big
result too big
999999999999999999999999999999 * 0
first number too big
``````

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am
i can't find where is the bug in my code
i hv checked all test cases in the board but still WA.....

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<sstream>
#include<ctype.h>
#include<math.h>

using namespace std;
long long  max = 2147483647;
char str[100000000];

int main()
{
string s;
char c;

while(gets(str)){
s=str;

long long  a=0,b=0,j,len,aflag=0,bflag=0,res,i,n,f;
f=0;
j=0;
len=s.length();
for(i=len;i>=0;i--){
if(isdigit(s[i])>0 && f==1){
a+=(s[i]-'0')*pow(10,j);
aflag=1;
j++;
}
else if(isdigit(s[i])>0 && f==0){
b+=(s[i]-'0')*pow(10,j);
j++;
bflag=1;
}
else if(s[i]=='-'){
if(bflag==1 && aflag==0){
b=b*(-1);
}
else if(bflag==1 && aflag==1){
a=a*(-1);
}

}
else if(isspace(s[i])>0 && j!=0){
j=0;
f=1;
}
else if(s[i]=='+'){
c='+';
j=0;
f=1;
}
else if(s[i]=='*'){
c='*';
j=0;
f=1;
}
}
//cout<<a<<endl<<b<<endl;
cout<<s<<endl;

if(c=='+')res=a+b;
else if(c=='*')res=a*b;

if(a>max)printf("first number too big\n");
if(b>max)printf("second number too big\n");
if(res>max)printf("result too big\n");
else continue;
}
return 0;
}``````
plzz help me

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
your a and b variable may overflow for inputs > 2^63 -1

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

### 465 : WA WA WA - Why??

Cant understand whay WA.Pls reply me . I have done this code using Big Number Summation and Big Number multiplication.
Then comparing the result length with the value "2147483647" .. But still WA WA WA WA WA WA

Is my input-Output format is correct ??? Need answer urgent

#include<stdio.h>
#include<ctype.h>
#include<string.h>

void BigMul(char *s1, char*s2, char *result);
void string_filter(char *s1, char*s2);
void Bigsum (char *str1,char *str2, char *sum);
void Rev(char *s);
void Big_sum (char *str1,char *str2, char *sum);

int main(void)
{
int i,m,len1,len2,maxlen,reslen;
char s1[1000],s2[1000],res[1000],c,result[1000], str[1000];

char max[]="2147483647";
maxlen=10;
while( true )
{
gets(str);
m=0;
for(i=0; ; i++)
{
if( str=='+' || str=='*' )
{
c=str;
break;
}

if(str==' ')
continue;

s1[m++]=str;
}
s1[m]='\0';

m=0;

for(++i; str ; i++)
{
if( str=='+' || str=='*' )
break;

if(str==' ')
continue;

s2[m++]=str;
}
s2[m]='\0';
//puts(s1); puts(s2);

string_filter(s1,s2);
len1=strlen(s1);
len2=strlen(s2);

if(c=='+')
Big_sum(s1,s2,res);
else if(c=='*')
BigMul(s1, s2, res);

reslen=strlen(res);
if(len1>maxlen)
{
printf("first number too big\n");
}
else if( len1==maxlen)
{
if( strcmp(max,s1) ==-1 )
{
printf("first number too big\n");
}
}

if(len2>maxlen)
{
printf("second number too big\n");
}
else if( len2==maxlen)
{
if( strcmp(max,s2) ==-1 )
{
printf("second number too big\n");
}
}

if(reslen>maxlen)
{
printf("result too big\n");
}
else if( reslen==maxlen)
{
if( strcmp(max,res) ==-1 )
{
printf("result too big\n");
}
}

}

}

void Big_sum (char *str1,char *str2, char *sum)
{
char ans[1000] ;
int carry=0, i , x ,j,m=0 ;

string_filter(str1 , str2);
i=strlen(str1)-1;
j=strlen(str2)-1;

while(i>=0 && j>=0)
{
x=str1[i]-'0'+str2[j]-'0'+carry;
ans[m]=(x%10)+'0' ;
carry = (x/10) ;
m++;
i--;
j--;
}

if(j==-1)
{
while(i>=0)
{
x=str1[i]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
i--;
}
}
else
{
while(j>=0)
{
x=str2[j]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
j--;
}
}

if(carry)
{
ans[m++]=carry+'0' ;
ans[m]='\0' ;
}
else
ans[m]='\0';

Rev(ans);
strcpy(sum,ans);

}

void BigMul(char *s1, char*s2, char *result)
{
char temp[10000], res[1000],n1[1000],sum[1000];
int a,b,i,k,carry=0,j,x,n,cross;

string_filter(s1 , s2);

if(s1[0]=='\0' || s2[0]=='\0')
{
strcpy(result,"0");
}
else
{

a=strlen(s1);
b=strlen(s2);

if(a < b)
{
strcpy(temp,s1);
strcpy(s1,s2);
strcpy(s2,temp);
a=strlen(s1);
b=strlen(s2);
}
cross=0;

for(j=b-1; j>=0; j--)
{
if(cross>=1)
{
for(k=0; k<cross; k++)
n1[k]='0';
}
else
k=0;
carry=0;

for(i=a-1; i>=0; i--,k++)
{
x=(((s2[j]-'0')*(s1[i]-'0'))+carry)%10;
n1[k]=x+'0';
carry=(((s1[i]-'0')*(s2[j]-'0'))+carry)/10;
}
if(carry)
n1[k++]=carry+'0';
n1[k]='\0';

if(cross==0)
{
for(n=0; n<k; n++)
sum[n]='0';
sum[n]='\0';
Rev(sum);
}
Rev(n1);
//puts(n1);
//strcpy(str1,n1);
Bigsum(n1 , sum , res);
strcpy(sum,res);
cross++;
}

strcpy(result, sum);
}

}

void string_filter(char *s1, char*s2) //removing leading zeros
{
int i,j,k;
char temp[1000];

for(i=0; s1[i]=='0'; i++);
for(j=i,k=0; s1[j]; j++)
temp[k++]=s1[j];

temp[k]='\0';
strcpy(s1,temp);

for(i=0; s2[i]=='0'; i++);
for(j=i,k=0; s2[j]; j++)
temp[k++]=s2[j];

temp[k]='\0';
strcpy(s2,temp);

}

void Bigsum (char *str1,char *str2, char *sum)
{
char ans[1000] ;
int carry=0, i , x ,j,m=0 ;
i=strlen(str1)-1;
j=strlen(str2)-1;

while(i>=0 && j>=0)
{
x=str1[i]-'0'+str2[j]-'0'+carry;
ans[m]=(x%10)+'0' ;
carry = (x/10) ;
m++;
i--;
j--;
}

if(j==-1)
{
while(i>=0)
{
x=str1[i]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
i--;
}
}
else
{
while(j>=0)
{
x=str2[j]-'0'+carry ;
ans[m++]=(x%10) +'0' ;
carry=(x/10);
j--;
}
}

if(carry)
{
ans[m++]=carry+'0' ;
ans[m]='\0' ;
}
else
ans[m]='\0';

Rev(ans);
strcpy(sum,ans);

}

void Rev(char *s)
{
char temp[10000];
int i,j=0;

for(i=strlen(s)-1; i>=0; i--,j++)
{
temp[j]=s[i];
}
temp[j]='\0';
strcpy(s,temp);

}