10106 - Product

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
New poster
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm
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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

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,t,t1,marker;
// to make the result 0, if one of the 2 numbers is 0...
if(aa=='0' && aa_l==1)
printf("0\n");
else if(bb=='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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem 10106

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

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

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

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
Contact:

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

thanx a looot man for ur advice.

i got it accepted...
Razib

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

10106 product

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

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, n2, product;

void getdigits(char s1, char s2) {
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 - '0';
for (i = strlen(s2) - 1, j = 501; i >= 0; i--, j--)
n2[j] = s2 - '0';
}

void multiply() {
char subtotal;
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 * 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, str2;
int i;

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

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

return 0;
}[/cpp]

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

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 in ['1'..'9'] then
begin check1:=false; break; end
else if s1='-' 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 in ['1'..'9'] then
begin check2:=false; break; end
else if s2='-' 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:=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)-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 >= 10 then
begin
inc(ans[i-1], ans div 10);
ans:=ans 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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
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, n2, product;

void getdigits(char s1, char s2) {
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 - '0';
for (i = strlen(s2) - 1, j = 501; i >= 0; i--, j--)
n2[j] = s2 - '0';
}

void multiply() {
char subtotal;
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 * 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, str2;
int i;

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

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

return 0;
}[/cpp]

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

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.