10106 - Product

[karl]

Friends,

I tried to solve 10106, but everytime judge's answer was "WA"
Statistics for 10106 says, that there are a lot of WA.

Well, do you have any hints, especially special cases?

Multiplication of 0 and empty lines in input file are no problem for my little proggie...

Thanks in advance!!!


Karl

[arc16]

are you calculating the result on-the-fly or using array?
if you're using array, maybe your array size is not big enough. the result will be around 500 digits.

[karl]

sorry, I went wrong. my algorithm for multiplication was incorrect.
It wasn't a wrong array size (I saw that X,Y <10 ^250!).

But thanks a lot for helping...

Best wishes

Karl

[razibcse]

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 300

void string_mul(char aa[],char bb[],long aa_l,long bb_l);
void main()
{
char num1[MAX],num2[MAX],max[MAX],min[MAX];
long max_length,min_length,num1_l,num2_l,a;

while(scanf("%s %s",num1,num2)==2)
 {
 num1_l=strlen(num1);
 num2_l=strlen(num2);

 // To find maximum & minimum of the 2 numbers.
 if(num1_l>=num2_l)
    {
    for(a=0;a<num1_l;a++)
      max[a]=num1[a];
    for(a=0;a<num2_l;a++)
      min[a]=num2[a];
    max_length=num1_l;
    min_length=num2_l;
    }
  else
    {
    for(a=0;a<num2_l;a++)
      max[a]=num2[a];
    for(a=0;a<num1_l;a++)
      min[a]=num1[a];
    max_length=num2_l;
    min_length=num1_l;
    }

 string_mul(max,min,max_length,min_length);
 }
}

void string_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[MAX][MAX],jj,sum,ii,result[500],t,t1,marker;
// to make the result 0, if one of the 2 numbers is 0...
if(aa[0]=='0' && aa_l==1)
  printf("0\n");
else if(bb[0]=='0' && bb_l==1)
  printf("0\n");
else
  {
y=0;
x=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);    //multiply the last digit of the 2 numbers...

      if(temp>=10)
           {
           i=temp%10;
           j=temp/10;       //add 'j' to the next...
           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]=ii;
        }
    else if(sum<10)
        {
        jj=0;
        result[i]=sum;
        }
    if(i==x_max && jj!=0)
        {
         for(;;)
            {
            t=jj%10;
            result[i++]=t;

            t1=jj/10;

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

 // to remove the leading zero's from the output, marker is used...
 for(t=i-1;t>=0;t--)
   if(result[t]!=0)
     {
     marker=t;
     break;
     }

 for(t=marker;t>=0;t--)
  printf("%ld",result[t]);

 printf("\n");
 }   //End of else statement....
}


[c][/c]

[Red Scorpion]

You must notice that 0<=x,y<10^250

try to bigger your array (max = 1000).
I hope this will help.

[razibcse]

thanx a looot man for ur advice.

i got it accepted...
Razib

[razibcse]

thanx a looot man for ur advice.

i got it accepted...
Razib

[route]

any tricky inputs for this question ?
I've deleted all leading zeros....
and it seems to work well with all numbers (including zero and negative number)
and it can deal with greater then 2 ^ 31 numbers...but it still got WA..

[ec3_limz]

Sorry that I used some very unorthodox array sizes.

I tried to simulate long multiplication, but got WA. Can anyone help?

[cpp]#include <stdio.h>
#include <string.h>

char n1[503], n2[503], product[503];

void getdigits(char s1[252], char s2[252]) {
int i, j;

memset(n1, 0, sizeof(n1));
memset(n2, 0, sizeof(n2));

for (i = strlen(s1) - 1, j = 501; i >= 0; i--, j--)
n1[j] = s1[i] - '0';
for (i = strlen(s2) - 1, j = 501; i >= 0; i--, j--)
n2[j] = s2[i] - '0';
}

void multiply() {
char subtotal[503];
int i, j, k;

memset(product, 0, sizeof(product));

for (i = 501; i >= 251; i--) {
memset(subtotal, 0, sizeof(subtotal));

for (j = 501, k = i; j >= 251; j--, k--) {
subtotal[k] += n1[i] * n2[j];
subtotal[k - 1] += subtotal[k] / 10;
subtotal[k] %= 10;
}

// add subtotal
for (j = 0; j < 502; j++)
product[j] += subtotal[j];
}
}

int main() {
bool lead;
char str1[252], str2[252];
int i;

while (scanf("%s%s", &str1, &str2) == 2) {
getdigits(str1, str2);
multiply();

lead = true;
for (i = 0; i < 502; i++) {
if (lead && product[i] > 0)
lead = false;
if (!lead)
printf("%d", product[i]);
}
if (lead)
printf("0");
printf("\n");
}

return 0;
}[/cpp]

[route]

I also got WA.... but i think i can deal with a variety of inputs
please help me...
<have made some changes of the program>
[pascal]
var s1, s2:string;
ans:array[-10..1000] of integer;
i, j, k, m, lb:longint;
check1, check2, neg:boolean;

begin
while not eof do
begin
lb:=1;
check1:=true;
check2:=true;
neg:=false;
readln(s1);
readln(S2);
while pos(' ', s1) <> 0 do
delete(s1, pos(' ',s1), 1);
while pos(' ', s2) <> 0 do
delete(s2, pos(' ',s2),1);
for i:=1 to length(s1) do
If s1[i] in ['1'..'9'] then
begin check1:=false; break; end
else if s1[i]='-' then
begin
delete(s1, i, 1);
neg:=not neg;
dec(i);
end;
If not check1 then delete(s1, 1, i-1);
for i:=1 to length(s2) do
If s2[i] in ['1'..'9'] then
begin check2:=false; break; end
else if s2[i]='-' then
begin
delete(s2, i, 1);
neg:=not neg;
dec(i);
end;
If not check2 then delete(s2, 1, i-1);
If (not check1) and (not check2) then begin
m:=0;
for i:=1 to 1000 do
ans[i]:=0;
k:=0;
for i:= length(s2) downto 1do
begin
for j:=length(s1) downto 1 do
begin
ans[i+j]:=ans[i+j]+(ord(s2[i])-48)*(ord(s1[j])-48)+k;
If ans[i+j] >= 10 then
begin
k:=ans[i+j] div 10;
ans[i+j]:=ans[i+j] mod 10;
end;
If i+j > m then m:=i+j;
end;
If k > 0 then
begin
inc(ans[i+j-1], k);
If i+j-1 > m then m:=i+j-1;
k:=0;
If i+j-1 < lb then lb:=i+j-1;
end;
end;
If neg then write('-');
i:=m+1;
repeat
dec(i);
If ans[i] >= 10 then
begin
inc(ans[i-1], ans[i] div 10);
ans[i]:=ans[i] mod 10;
end;
until (i<=lb) and (ans[i-1] < 10);
while ans[lb] = 0 do inc(lb);
for i:=lb to m do
write(ans[i]);
writeln;
end
else writeln(0);
end;
end.
[/pascal]

[Dominik Michniewski]

What's our answer for inputs like this:

Code: Select all

000000000 0000000000000000
0000005    000000000005


Maybe this help us
I don't execute our code - maybe we are right answer for this question, but ...

Regards
Dominik

[route]

I have doubts about the input format:
Doesn't it have two seperate lines for a pair of inputs?
e.g.
12
12
144<--- output

And are there any tricky inputs other than trailing and leading spaces in inputs, negative numbers, zero in inputs (these are what my problem has solved)?

[Dominik Michniewski]

you have right - one input test is pair of line I don't remember about it, but If you read input like scanf("%s",...) it doesn't matter ....

I don't know other tricks .... Perhaps zero is only special case ...
I think, that you must have error in functions computing result ... Maybe some carry sign is missing . I don't know ....

Regards
Dominik

[ec3_limz]

Hi everyone,

I have later discovered my mistake. My mistake is that in adding the subtotal, I FORGOT TO CARRY OVER WHEN A DIGIT IS MORE THAN 10. And now I got this problem Accepted

For those of you having trouble with this problem, here is my Accepted source code.

[cpp]#include <stdio.h>
#include <string.h>

char n1[503], n2[503], product[503];

void getdigits(char s1[252], char s2[252]) {
int i, j;

memset(n1, 0, sizeof(n1));
memset(n2, 0, sizeof(n2));

for (i = strlen(s1) - 1, j = 501; i >= 0; i--, j--)
n1[j] = s1[i] - '0';
for (i = strlen(s2) - 1, j = 501; i >= 0; i--, j--)
n2[j] = s2[i] - '0';
}

void multiply() {
char subtotal[503];
int i, j, k;

memset(product, 0, sizeof(product));

for (i = 501; i >= 251; i--) {
memset(subtotal, 0, sizeof(subtotal));

for (j = 501, k = i; j >= 251; j--, k--) {
subtotal[k] += n1[i] * n2[j];
subtotal[k - 1] += subtotal[k] / 10;
subtotal[k] %= 10;
}

// add subtotal
for (j = 501; j > 0; j--) {
product[j] += subtotal[j];
product[j - 1] += product[j] / 10;
product[j] %= 10;
}
}
}

int main() {
bool lead;
char str1[252], str2[252];
int i;

while (scanf("%s%s", &str1, &str2) == 2) {
getdigits(str1, str2);
multiply();

lead = true;
for (i = 0; i < 502; i++) {
if (lead && product[i] > 0)
lead = false;
if (!lead)
printf("%d", product[i]);
}
if (lead)
printf("0");
printf("\n");
}

return 0;
}[/cpp]

[zsepi]

any tricky inputs for this question ?

hmm, let's see... have you tried multiplying with zero? and what's the upper limit for the numbers you can deal with? I got AC on it and I prepared to deal with any number less than 10^1000... maybe you can't use long long and those kinda things :)