10106 - Product

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

Moderator: Board moderators

10106 - Product

Postby karl » Wed Aug 28, 2002 3:41 pm

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
karl
New poster
 
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

Postby arc16 » Wed Aug 28, 2002 4:38 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

Postby karl » Thu Aug 29, 2002 9:40 am

sorry, I went wrong. my algorithm for multiplication was incorrect. :oops:
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..

Postby razibcse » Tue Dec 10, 2002 5:02 pm

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
Location: SUST,BANGLADESH

Problem 10106

Postby Red Scorpion » Mon Dec 23, 2002 5:17 am

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

Postby razibcse » Mon Dec 23, 2002 2:16 pm

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
Location: SUST,BANGLADESH

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

Postby razibcse » Mon Dec 23, 2002 2:17 pm

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
Location: SUST,BANGLADESH

10106 product

Postby route » Tue Dec 31, 2002 1:00 pm

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..
route
New poster
 
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

10106

Postby ec3_limz » Thu Jan 09, 2003 5:02 pm

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

Re: #10106: Product - WA

Postby route » Fri Jan 10, 2003 8:00 am

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

Postby Dominik Michniewski » Fri Jan 10, 2003 9:19 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

Postby route » Fri Jan 10, 2003 12:17 pm

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

Postby Dominik Michniewski » Fri Jan 10, 2003 12:55 pm

you have right - one input test is pair of line :oops: 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

Postby ec3_limz » Fri Jan 10, 2003 1:10 pm

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

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

Re: 10106 product

Postby zsepi » Wed Jan 15, 2003 11:42 am

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

Return to Volume CI

Who is online

Users browsing this forum: sajal2k8 and 0 guests