## 10106 - Product

Moderator: Board moderators

### 10106 - Product

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

Karl
karl
New poster

Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

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.
arc16
Learning poster

Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

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
karl
New poster

Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

### 10106: Why WA??? tell me someone..

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]
razibcse
New poster

Posts: 50
Joined: Mon Jul 22, 2002 3:17 am

### Problem 10106

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

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

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### Thanx a lot man!!!

thanx a looot man for ur advice.

i got it accepted...
Razib
razibcse
New poster

Posts: 50
Joined: Mon Jul 22, 2002 3:17 am

### Thanx a lot man!!!i got it accepted...

thanx a looot man for ur advice.

i got it accepted...
Razib
razibcse
New poster

Posts: 50
Joined: Mon Jul 22, 2002 3:17 am

### 10106 product

any tricky inputs for this question ?
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..
route
New poster

Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

### 10106

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

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

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

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

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

return 0;
}[/cpp]
ec3_limz
Learning poster

Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### Re: #10106: Product - WA

I also got WA.... but i think i can deal with a variety of inputs
<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;
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]
Last edited by route on Sat Jan 11, 2003 4:31 am, edited 2 times in total.
route
New poster

Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

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
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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)?
route
New poster

Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

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
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

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

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

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

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

return 0;
}[/cpp]
ec3_limz
Learning poster

Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### Re: 10106 product

route wrote: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 :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Next