465 - Overflow

[Subeen]

please give the output format of the following input

00009999 + 99999
9999+00099999
9999

+
00009



<font size=-1>[ This Message was edited by: Subeen on 2002-04-06 16:38 ]</font>

[Stefan Pochmann]

00009999 + 99999
9999 + 00099999
9999 + 00009

[Subeen]

stefan, my program gives same output, but why does it get W.A.???

[Stefan Pochmann]

That's because there are other inputs where yours and mine give different results.

Btw, "int" has 32 bit, not 16.

[Subeen]

i used 4 bit int. still W.A.
i need some inputs and outputs.

[C8H10N4O2]

I hope you mean 4 "byte" int. 4 bit int is just silly:o)

[Subeen]

sorry surely it is 4 byte.
but this prog. still gives me a lot of trouble.
plz help.
thankx.

[Neo]

Subeen, Try the input: ( output is not big! !)
If you did not tried already.

Input:
0*9999999999990999999999999

Output:
0*9999999999990999999999999
second number too big

[Subeen]

still WA. here is my code:

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

#define MAX 1000000

int myStrCmp(char a[], char b[])
{
int lena, lenb;
lena = strlen(a);
lenb = strlen(b);
if(lena > lenb) return 1;
else if(lena < lenb) return -1;
else return strcmp(a, b);
}

void main()
{
char s1[MAX], s2[MAX];
char ch;
long i, num1, num2, num;
int flag, flag1, flaga, flagm, f;

while(1)
{
flaga = flagm = flag = 0;
flag1 = 0;
i = 0;
f = 0;
while((ch=getchar())!=EOF)
{
f = 1;
putchar(ch);
if(ch=='\n') break;
if(ch=='*')
{
if(!i) s1[i++] = '0';
s1 = 0;
i = 0;
flag = 1;
flag1 = 0;
continue;
}
else if(ch=='+')
{
if(!i) s1[i++] = '0';
s1 = 0;
i = 0;
flag = 2;
flag1 = 0;
continue;
}

if(!flag)
{
if(ch!='0')
flag1 = 1;
if(flag1)
s1[i++] = ch;
}
else
{
if(ch!='0')
flag1 = 1;
if(flag1)
s2[i++] = ch;
}
}
if(!f) break;
if(!i) s2[i++] = '0';
s2 = 0;

if(1==myStrCmp(s1, "2147483647"))
{
printf("first number too big\n");
flaga = flagm = 1;
}

if(1==myStrCmp(s2, "2147483647"))
{
printf("second number too big\n");
flaga = flagm = 1;
if(flag==2)
printf("result too big\n");
}

if(flag==2)
{
if(flaga)
printf("result too big\n");
else
{
num1 = atol(s1);
num2 = atol(s2);
num = 2147483647 - num1;
if(num2 > num)
printf("result too big\n");
}
}
else if(flag==1)
{
if(!strcmp(s1, "0") || !strcmp(s2, "0"));
else
{
if(flagm)
printf("result too big\n");
else
{
num1 = atol(s1);
num2 = atol(s2);
num = 2147483647 / num1;
if(num2 > num)
printf("result too big\n");
}
}
}

if(ch==EOF) break;

}
}
[/c]

[IIUC GOLD]

You can solve this problem by using log().

lim = log(INT_MAX);

res = log(num1 + num2);
num1 = log(num1);
num2 = log(num2);

if (num1 > lim)
printf("first number too big\n");
if (num2 > lim)
printf("second number too big\n");
if (op == '+' && res > lim)
printf("result too big\n");
if (op == '*' && (num1+num2) > lim)
printf("result too big\n");

[Abednego]

How could this possibly be a WA!? Assuming, of course, that my BigInt is flawless ;-) I've tested it on about 15 problems so far, so I have reason to believe that it is.
[cpp]
BigInt a, b, m( 0x7FFFFFFF );
char c;
while( cin >> a >> c >> b )
{
cout << a << " " << c << " " << b << endl;
if( a > m ) cout << "first number too big" << endl;
if( b > m ) cout << "second number too big" << endl;
BigInt r = ( c == '+' ? a + b : a * b );
if( r > m ) cout << "result too big" << endl;
}
[/cpp]

[Yarin]

First, Bigint isn't required in this problem. I used long long and got it working. Your error is, I guess, that you don't output the input correctly. You should basically just echo the input. In your program, you both remove leading zeros and add/remove whitespaces (there might, I think, be no white space between the numbers and the operator).

[Abednego]

Thank you very much. That did it. Although it is a fluke that long long works. One can easily cook up a test case where this solution would give a wrong answer. For example, if one of the inputs is (2 * LONG_LONG_MAX_VALUE + 100).

[Yarin]

Actually, I was a bit too quick there. I don't actually scanf the input value into a long long, I read it digit by digit, store it in a long long (old=old*10+digit), and when it becomes >MAXINT, I set an overflow flag. Thus each number consist of a long long and an overflow bit.

[htl]

Here's my code. It alway got RE. Could someone give me some data that may cause my prog RE?
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
void main(void)
{
int x,len1,len2,y,len,num1[10],num2[10],ans[20],lim[10],p1,p2,overflow,first,second,z,a;
char s[1000],oper,*t;
while(gets(s)!=NULL)
{
for(x=0;s[x]!='\0';x++)
if(s[x]=='+' || s[x]=='*')
{
oper=s[x];
break;
}
printf("%s\n",s);
for(x=0;x<10;x++)
num1[x]=num2[x]=0;
for(x=0;x<20;x++)
ans[x]=0;
first=second=overflow=NO;
len1=len2=0;
lim[0]=2,lim[1]=1,lim[2]=4,lim[3]=7,lim[4]=4,lim[5]=8,lim[6]=3,lim[7]=6,lim[8]=4,lim[9]=7;
t=strtok(s," +*");
len=strlen(t);
for(x=0;x<len;x++)
if(t[x]>='1' && t[x]<='9')
break;
if(x==len)
{
num1[9]=0;
len1=1;
}
else if(len-x>10)
printf("first number too big\n"),first=YES;
else
{
for(y=9,z=len-1,a=0;z>=x && y>=0;z--,y--)
num1[y]=t[z]-'0',a++;
len1=a;
if(a==10)
{
for(x=0;x<10;x++)
if(lim[x]!=num1[x])
break;
if(x<10 && lim[x]<num1[x])
printf("first number too big\n"),first=YES;
}
}
t=strtok(0," +*");
len=strlen(t);
for(x=0;x<len;x++)
if(t[x]>='1' && t[x]<='9')
break;
if(x==len)
{
num2[9]=0;
len2=1;
}
else if(len-x>10)
printf("second number too big\n"),second=YES;
else
{
for(y=9,z=len-1,a=0;z>=x && y>=0;z--,y--)
num2[y]=t[z]-'0',a++;
len2=a;
if(a==10)
{
for(x=0;x<10;x++)
if(lim[x]!=num2[x])
break;
if(x<10 && lim[x]<num2[x])
printf("second number too big\n"),second=YES;
}
}
if((num1[9]==0 && len1==1 && first!=YES || num2[9]==0 && len2==1 && second!=YES) && oper=='*')
continue;
if(first==YES && len1==0 || second==YES && len2==0)
{
printf("result too big\n");
continue;
}
if(oper=='+')
{
if(len1>=len2)
y=len1;
else
y=len2;
for(x=0;x<y;x++)
{
if(x<len1)
ans[19-y]+=num1[9-x];
if(x<len2)
ans[19-y]+=num2[9-x];
}
for(x=19;x>0;x--)
if(ans[x]>=10)
ans[x]-=10,ans[x-1]++;
}
else
{
for(p1=0;p1<len1;p1++)
for(p2=0;p2<len2;p2++)
ans[19-p1-p2]+=num1[9-p1]*num2[9-p2]%10,ans[19-p1-p2-1]+=num1[9-p1]*num2[9-p2]/10;
for(x=19;x>0;x--)
ans[x-1]+=ans[x]/10,ans[x]%=10;
}
for(x=0;x<20;x++)
if(ans[x]!=0)
break;
if(x<10)
overflow=YES;
if(x==10)
{
for(y=0;y<10 && x<20;x++,y++)
if(lim[y]!=ans[x])
break;
if(y<10 && lim[y]<ans[x])
overflow=YES;
}
if(overflow)
printf("result too big\n");
}
}
[/c]