465 - Overflow

htl · Post by **htl** » Sat Dec 07, 2002 7:05 am

This time I use long long rather than bignum. But it still get RE. I think there's something wrong with my input handling. Could someone help me?
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
void main(void)
{
int x,len,f_flag,s_flag;
long long first,second;
char s[1000],oper,*t;
while(gets(s)!=NULL)
{
printf("%s\n",s);
for(x=0;s[x]!='\0';x++)
if(s[x]=='+' || s[x]=='*')
{
oper=s[x];
break;
}
f_flag=s_flag=NO;
t=strtok(s," +*");
len=strlen(t);
for(x=0;x<len;x++)
if(t[x]>='1' && t[x]<='9')
break;
if(x==len)
first=0;
else if(len-x>10)
printf("first number too big\n"),f_flag=YES;
else
{
for(first=0;x<len;x++)
first=first*10+t[x]-'0';
if(first>2147483647)
printf("first number too big\n"),f_flag=YES;
}
t=strtok(0," +*");
len=strlen(t);
for(x=0;x<len;x++)
if(t[x]>='1' && t[x]<='9')
break;
if(x==len)
second=0;
else if(len-x>10)
printf("second number too big\n"),s_flag=YES;
else
{
for(second=0;x<len;x++)
second=second*10+t[x]-'0';
if(second>2147483647)
printf("second number too big\n"),s_flag=YES;
}
if(oper=='*' && (!f_flag && first==0 || !s_flag && second==0))
continue;
if(f_flag || s_flag)
{
printf("result too big\n");
continue;
}
if(oper=='+' && first+second>2147483647 || oper=='*' && first*second>2147483647)
printf("result too big\n");
}
}
[/c]

razibcse · Post by **razibcse** » Tue Feb 18, 2003 2:17 am

hi,
This is also getting CE as 495...
what's the problem u think I have in my code..

here's my code:

Code: Select all



#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000
#define MAXSZ 500
#define MAXARRAY 10000
#define MAX_INT 32767

void str_add(char first[],char second[],long len1,long len2);
void str_mul(char aa[],char bb[],long aa_l,long bb_l);

void main()
{
long flag,len1,len2,num1,num2;
char ch,first[MAXARRAY],second[MAXARRAY],str[MAXARRAY];
while(gets(str))
 {
 sscanf(str,"%s %c %s",first,&ch,second);
 len1=strlen(first);
 len2=strlen(second);

 printf("%s\n",str);

 flag=1;
 if(len1>5)
   {
   flag=0;
   printf("first number too big\n");
   }
 else if(len1==5)
   {
   flag=1;
   num1=atol(first);
   if(num1>MAX_INT)
      {
      flag=0;
      printf("first number too big\n");
      }
   else if(num1<=MAX_INT)
      flag=1;
   }

 if(len2>5)
   {
   flag=0;
   printf("second number too big\n");
   }

 else
 if(len2==5)
   {
   flag=1;
   num2=atol(second);
   if(num2>MAX_INT)
      {
      flag=0;
      printf("second number too big\n");
      }
   else if(num2<=MAX_INT)
      flag=1;
   }

 if(flag==0)
  printf("result too big\n");
 else
 if(flag==1)
   {
   if(ch=='+')
     str_add(first,second,len1,len2);
   else if(ch=='*')
     str_mul(first,second,len1,len2);
   }
 }
}

void str_add(char first[],char second[],long len1,long len2)
{
long sum,max,min,dif,re,qu,num,a,i,j,k,x,y,len;
char result[MAXARRAY];

if(len1>=len2)
 {
 max=len1;
 min=len2;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   second[a+dif]=second[a];

 for(a=0;a<dif;a++)
   second[a]='0';

 }
else if(len1<len2)
 {
 max=len2;
 min=len1;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   first[a+dif]=first[a];

 for(a=0;a<dif;a++)
   first[a]='0';

 }

qu=0;

i=MAX-1;
for(a=max-1;a>=0;a--)
  {
  sum=qu+(first[a]-48)+(second[a]-48);

  if(sum>=10)
    {
    qu=sum/10;
    re=sum%10;
    }
  else if(sum<10)
    {
    qu=0;
    re=sum;
    }
  result[i--]=(char)(re+48);
  if(a==0 && qu!=0)
    {
    for(;;)
        {
        x=qu/10;
        y=qu%10;
        result[i--]=char(y+48);
        if(x==0) break;
        qu=x;
        }
    }
  }
j=i+1;
k=MAX-1-j;

for(i=j;i<=MAX;i++)
  result[i-j]=result[i];
result[k+1]='\0';

 len=strlen(result);
 if(len>5)
   printf("result too big\n");
 else if(len==5)
   {
   num=atol(result);

   if(num>MAX_INT)
     printf("result too big\n");
   }
}

void str_mul(char aa[],char bb[],long aa_l,long bb_l)
{
long a,b,temp,i,j,mul1,mul2,x,y,x_max,x_last[MAX],y_final;
long re[MAXSZ][MAXSZ],jj,sum,ii,t,t1,marker,sum1;
char result[5000];

y=0;

x_max=0;
for(b=bb_l-1;b>=0;b--)
  {
  mul1=bb[b]-48;
  x=y;
  j=0;

  for(a=aa_l-1;a>=0;a--)
      {
      mul2=aa[a]-48;
      temp=j+(mul1*mul2);

      if(temp>=10)
           {
           i=temp%10;
           j=temp/10;
           re[y][x]=i;
           }
      else if(temp<10)
           {
           i=temp;
           j=0;
           re[y][x]=i;
           }
      if(a==0)
           {
           x++;
           re[y][x]=j;
           x_last[y]=x;

           }
       if(a!=0)
        x++;
       }
   y++;
   if(x>x_max)
      x_max=x;
   }

  y_final=y;

  for(j=1;j<y_final;j++)
    for(i=0;i<j;i++)
        {
        re[j][i]=0;
        }
  for(j=0;j<y_final;j++)
    for(i=x_last[j]+1;i<=x_max;i++)
        {
        re[j][i]=0;
        }
  jj=0;

  for(i=0;i<=x_max;i++)
    {
    sum=0;
    for(j=0;j<y_final;j++)
      sum+=re[j][i];
      sum+=jj;
    if(sum>=10)
        {
        ii=sum%10;
        jj=sum/10;
        result[i]=(char)(ii+'0');
        }
    else if(sum<10)
        {
        jj=0;
        result[i]=(char)(sum+'0');
        }
    if(i==x_max && jj!=0)
        {
         for(;;)
            {
            t=jj%10;
            result[i++]=(char)(t+'0');

            t1=jj/10;

            if(t1<10)
              {
              result[i++]=(char)(t1+'0');
              break;
              }
            t=t1;
            }
        }
    }


 for(t=i-1;t>=0;t--)
   if(result[t]!='0')
     {
     marker=t;
     break;
     }


 if(marker>4)
 printf("result too big\n");
else if(marker==4)
  {
  sum1=0;
  for(t=marker;t>=0;t--)
    sum1+=(result[t]-'0')*pow(10,t);

  if(sum1>MAX_INT)
   printf("result too big\n");
  }

}

afonsocsc · Post by **afonsocsc** » Mon Mar 24, 2003 11:50 pm

Don't know why this gives wa!
Anyone can help me?...
[c]
...
[/c]

turuthok · Post by **turuthok** » Tue Mar 25, 2003 12:52 am

I honestly haven't solved this problem but I did take a look on the problem descriptions, especially on Input and Output sections.

We know that each line of input might have leading or trailing white-spaces ... If the judge is evil enough and requires the output should be exactly the same as how it is presented on the input, ... then I'm sure you'll fail this because your code doesn't output the extra white-space(s).

-turuthok-

afonsocsc · Post by **afonsocsc** » Tue Mar 25, 2003 1:18 am

I forgot that!...
Changed code and put spaces everywhere on the input (not inside the numbers) and the output was identically, but still wa!...
[c]
...
[/c]

turuthok · Post by **turuthok** » Tue Mar 25, 2003 1:35 am

Hello, I made an observation on this following code:

[c]#include <stdio.h>

int main() {
long long a = 0;
char *p = "9999999999";

sscanf(p, "%lld", &a);

printf("%s\n", p);
printf("%lld\n", a);
return 0;
}
[/c]

I used gcc and the output doesn't really make sense, ... probably it's better to parse the integer yourself. I remember we talked about scanf() won't handle this "long long" data-type.

-turuthok-

afonsocsc · Post by **afonsocsc** » Tue Mar 25, 2003 3:26 pm

Changed, but that's not it...
There's something that's giving wa, but I just can't see it!
[c]
...
[/c]

turuthok · Post by **turuthok** » Tue Mar 25, 2003 9:24 pm

Okay, there's only one thing that I can think of ... I'll try to solve this one, too ...

If this following input is allowed and used by the judge, your solution will fail.

000000000000000000011+1

-turuthok-

afonsocsc · Post by **afonsocsc** » Tue Mar 25, 2003 9:29 pm

It was that!!! I forgot to check the zeros!

Thanks a lot!!!
Finally got ac!

anupam · Post by **anupam** » Wed Mar 26, 2003 6:34 am

always try to think about the cases of zero...
in some cases only zeros make very poor result of programs...
just think specially about zero whether or not it is needed..
perhaps this will help u to solve other probs...

anupam

Almost Human · Post by **Almost Human** » Thu Apr 17, 2003 8:02 am

i guess because you use "void main"

you better try to use "int main" and add "return 0 ;" at the end of your code.

rjhadley · Post by **rjhadley** » Tue Apr 22, 2003 2:47 am

its probably too late to help you now, but on line 133:
[c]
result[i--]=char(y+48);
[/c]
perhaps you mean something like:
[c]
result[i--]=(char)(y+48);
[/c]

soyoja · Post by **soyoja** » Sat May 03, 2003 3:04 pm

I use my own BigInt class to solve this problem.

My bigInt class works well ( I solved problem 10106 with this class )

I checked input with leading zeros and white space.

( I use cin.getline function )

But I still got WA again and again...

Maybe judging system use very critical input data.... But I can't find that.

If anyone have good input data for testing, please help me.

Thanks.

Maxim · Post by **Maxim** » Sun May 04, 2003 11:42 pm

Here are few tests:

input:

2000000000 + 2000000000
1000000 * 1000000

output:

2000000000 + 2000000000
result too big
1000000 * 1000000
result too big

I've solved it without BigInt.

Maxim

soyoja · Post by **soyoja** » Wed May 07, 2003 5:36 am

Ok... I found small mistake which caused WA.
Finally, I got accepted. : )

Maxim, you are right. I tested two type of code, one use Bigint class,
another use long long datatype. Both solution accepted.
Therefore, I found that test data don't exceed long long type integer.
Thanks.

P.S ) Here is my other samples...

Input
2147483647 * 1
2147483647 + 1
0 * 1000000000000
2147483648 * 0

Output
2147483647 * 1
2147483647 + 1
result too big
0 * 1000000000000
second number too big
2147483648 * 0
first number too big

OJ Board

465 - Overflow

465:why It's getting compile error?

465 WA

465 - Overflow