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

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Wed Jun 01, 2005 2:12 pm

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

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

Reply

Post by Rocky » Thu Jun 02, 2005 7:08 am

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

THANK"S IN ADVANCE
Rocky

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

Post by Sedefcho » Sat Jun 11, 2005 8:49 pm

Rocky,

I suggest you check the old threads about this problem.

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

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

Thank's For Help

Post by Rocky » Sun Jun 12, 2005 6:02 am

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

Rocky

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Tue Jun 14, 2005 11:46 pm

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!

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Fri Jul 01, 2005 4:23 pm

my critical in/out was

Code: Select all

000000000000000000000000000000000000000000000000000000000000000000000009999999999999999999999999999999999999999999999999999999999 + 1
Regards
keep it real!

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Fri Jul 01, 2005 5:27 pm

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!

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

465 need a hand filled by help

Post by tuman » Sat Oct 22, 2005 8:17 pm

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

Post by Solaris » Sat Oct 22, 2005 9:44 pm

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?

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

Post by tuman » Sun Oct 23, 2005 11:56 pm

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. :lol: But i would also like to thank Tanvir (Aatel) for notifying me this problem. :wink:
We the dreamer of the dreamy dream...

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

wtf?????

Post by rmotome » Tue Aug 08, 2006 1:36 am

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:

Post by mf » Tue Aug 08, 2006 1:52 am

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

Post by Iffat » Sat Aug 04, 2007 7:42 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
thanx in advance

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Aug 04, 2007 2:40 pm

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??

Post by tanvir_cse » Sat Nov 22, 2008 8:31 pm

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

}

Post Reply

Return to “Volume 4 (400-499)”