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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

465:why It's getting compile error?

Post by razibcse »

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
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

465 WA

Post by afonsocsc »

Don't know why this gives wa!
Anyone can help me?...
[c]
...
[/c]
Last edited by afonsocsc on Fri Apr 11, 2003 12:46 pm, edited 1 time in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc »

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]
Last edited by afonsocsc on Fri Apr 11, 2003 12:47 pm, edited 1 time in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc »

Changed, but that's not it...
There's something that's giving wa, but I just can't see it!
[c]
...
[/c]
Last edited by afonsocsc on Fri Apr 11, 2003 12:48 pm, edited 1 time in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

Post by afonsocsc »

It was that!!! I forgot to check the zeros! :o
Thanks a lot!!!
Finally got ac! :D

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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
"Everything should be made simple, but not always simpler"

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human »

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
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley »

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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

465 - Overflow

Post by soyoja »

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
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim »

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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja »

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

Post Reply

Return to “Volume 4 (400-499)”