## 338 - Long Multiplication

Moderator: Board moderators

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### 338

Huff, finally I got Accepted on this problem . But I still got PE, it doesn't matter.
Thx Andrey Mokhov for your help.

Regards
Angga888

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: 338

angga888 wrote:Huff, finally I got Accepted on this problem .
Could you let us know what is your output to:

Code: Select all

1100 33
33 1100
33 101
33 100010
0
Thanks,
HoraPe

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

### 338

i have some questions.
1.Is their any negetive integer?
2.is their any superfluous 0s at the beginning of the integer?
3.if input is 1010,1010 what's the output?
khobaib

Ianchen
New poster
Posts: 2
Joined: Sun Oct 03, 2004 6:30 pm

### 338 WA I try many time to solve it ,but can't

[c]

Code: Select all

#include<stdio.h>
#include<string.h>
#include <stdlib.h>

char a[100],*b[2],c[20][20],d[20];
int len1,len2,i,j,max,templen;
char temp[20];

void mul()
{
int carry,temp1,i,j,k;
char temp2;
for (j=0;j<len2;j++)
{
carry=0;
for (i=0;i<len1;i++)
{
if (c[1][j]!='0')
{
temp1=((c[0][i]-48)*(c[1][j]-48)+carry)%10;
carry=((c[0][i]-48)*(c[1][j]-48)+carry)/10;
c[2+j][i+j]=temp1+48;
}
else
{
c[2+j][i+j]='\0';
carry=0;
}
}
if (carry!=0)
c[2+j][len1+j]=carry+48;
else
c[2+j][len1+j]='\0';
for (k=len1+1+j;k<20;k++)
c[2+j][k]='\0';
}
for (i=0;i<20;i++)
temp[i]=c[2][i];
for (j=3;j<len2+2;j++)
{
carry=0;
for (i=0;i<len1+len2;i++)
{
if (c[j][i]=='\0')
if (temp[i]!='\0')
temp[i]+=carry;
else if (i>=max&&carry==0)
temp[i]='\0';
else
temp[i]=carry+48;
else
{
if (temp[i]!='\0')
{
temp2=temp[i];
temp[i]=((carry+temp[i]+c[j][i]-96)%10)+48;
carry=(carry+temp2+c[j][i]-96)/10;
}
else
{
temp2=0;
temp[i]=((carry+temp[i]+c[j][i]-48)%10)+48;
carry=(carry+temp2+c[j][i]-48)/10;
}
}
}
}
}
int main(void)
{
freopen("data.txt","r",stdin);
while (1)
{
gets(a);
for (i=0;i<strlen(a);i++)
if (a[i]==9)
a[i]=' ';
b[0]=strtok(a," ");
b[1]=strtok(NULL," ");
if ((atoi(b[0])==0) && (b[1]==NULL))
return 0;
if (atoi(b[0])==0)
b[0]="0";
else if (b[0][0]=='0')
{
templen=strlen(b[0]);
for (i=0;i<templen;i++)
{
if (b[0][0]!='0')
break;
b[0]=&b[0][1];
}
}
if (atoi(b[1])==0)
b[1]="0";
else if (b[1][0]=='0')
{
templen=strlen(b[1]);
for (i=0;i<templen;i++)
{
if (b[1][0]!='0')
break;
b[1]=&b[1][1];
}
}
len1=strlen(b[0]);
len2=strlen(b[1]);
j=0;
for (i=0;i<20;i++)
if (b[1][i]!='0')
d[j++]=b[1][i];
for (i=0;i<len1;i++)
c[0][i]=b[0][len1-i-1];
c[0][len1]='\0';
for (i=0;i<len2;i++)
c[1][i]=b[1][len2-i-1];
c[1][len2]='\0';
max=0;
if (len1>=len2)
max=len1;
else
max=len2;
mul();
if ((strcmp(b[1],"0")!=0) && (strcmp(b[0],"0")!=0))
{
for (i=0;i<(strlen(temp)-len1);i++)
printf(" ");
printf("%s\n",b[0]);
for (i=0;i<(strlen(temp)-len2);i++)
printf(" ");
printf("%s\n",b[1]);
for (i=0;i<strlen(temp)-max;i++)
printf(" ");
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
else if (strcmp(b[1],"0")==0)
{
printf("%s\n",b[0]);
for (i=0;i<(len1-len2);i++)
printf(" ");
printf("0\n");
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
else
{
for (i=0;i<(len2-len1);i++)
printf(" ");
printf("0\n");
printf("%s\n",b[1]);
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
for (j=0;j<len2;j++)
{
if ((c[1][j]!='0')&&(atoi(c[0])!=0)&&(strlen(d)!=1))
{
for (i=0;i<len1+len2;i++)
printf("%c",c[j+2][strlen(temp)-i-1]);
printf("\n");
}
else if ((len1==1 && len2==1)&&(c[1][j]!='0')&&(atoi(c[0])!=0))
{
for (i=0;i<len1+len2;i++)
printf("%c",c[j+2][strlen(temp)-i-1]);
printf("\n");
}
}
if ((atoi(c[0])!=0) && (len1!=1 || len2!=1)&&(atoi(c[1])!=0)&&(strlen(d)!=1))
{
for (i=0;i<strlen(temp);i++)
printf("-");
printf("\n");
}
if ((atoi(c[0])!=0) && (atoi(c[1])!=0))
{
if (len1!=1||len2!=1)
{
for (i=0;i<len1+len2;i++)
printf("%c",temp[strlen(temp)-i-1]);
printf("\n");
}
}
else
{
for (i=0;i<max-1;i++)
printf(" ");
printf("0");
printf("\n");
}
printf("\n");
}
return 0;
}[color=darkred][/color][color=#444444][/color][size=7][/size]
[/c]

Ianchen
New poster
Posts: 2
Joined: Sun Oct 03, 2004 6:30 pm

Code: Select all

[c]#include<stdio.h>
#include<string.h>
#include <stdlib.h>

char a[100],*b[20],c[20][20],d[20];
int len1,len2,i,j,max,templen;
char temp[20];

void mul()
{
int carry,temp1,i,j,k;
char temp2;
for (j=0;j<len2;j++)
{
carry=0;
for (i=0;i<len1;i++)
{
if (c[1][j]!='0')
{
temp1=((c[0][i]-48)*(c[1][j]-48)+carry)%10;
carry=((c[0][i]-48)*(c[1][j]-48)+carry)/10;
c[2+j][i+j]=temp1+48;
}
else
{
c[2+j][i+j]='\0';
carry=0;
}
}
if (carry!=0)
c[2+j][len1+j]=carry+48;
else
c[2+j][len1+j]='\0';
for (k=len1+1+j;k<20;k++)
c[2+j][k]='\0';
}
for (i=0;i<20;i++)
temp[i]=c[2][i];
for (j=3;j<len2+2;j++)
{
carry=0;
for (i=0;i<len1+len2;i++)
{
if (c[j][i]=='\0')
if (temp[i]!='\0')
temp[i]+=carry;
else if (i>=max&&carry==0)
temp[i]='\0';
else
{
temp[i]=carry+48;
carry=0;
}
else
{
if (temp[i]!='\0')
{
temp2=temp[i];
temp[i]=((carry+temp[i]+c[j][i]-96)%10)+48;
carry=(carry+temp2+c[j][i]-96)/10;
}
else
{
temp2=0;
temp[i]=((carry+temp[i]+c[j][i]-48)%10)+48;
carry=(carry+temp2+c[j][i]-48)/10;
}
}
}
}
}
int main(void)
{
freopen("data.txt","r",stdin);
while (1)
{
gets(a);
for (i=0;i<strlen(a);i++)
if (a[i]==9)
a[i]=' ';
b[0]=strtok(a," ");
b[1]=strtok(NULL," ");
if ((atoi(b[0])==0) && (b[1]==NULL))
return 0;
if (atoi(b[0])==0)
b[0]="0";
else if (b[0][0]=='0')
{
templen=strlen(b[0]);
for (i=0;i<templen;i++)
{
if (b[0][0]!='0')
break;
b[0]=&b[0][1];
}
}
if (atoi(b[1])==0)
b[1]="0";
else if (b[1][0]=='0')
{
templen=strlen(b[1]);
for (i=0;i<templen;i++)
{
if (b[1][0]!='0')
break;
b[1]=&b[1][1];
}
}
len1=strlen(b[0]);
len2=strlen(b[1]);
j=0;
for (i=0;i<20;i++)
if (b[1][i]!='0')
d[j++]=b[1][i];
for (i=0;i<len1;i++)
c[0][i]=b[0][len1-i-1];
c[0][len1]='\0';
for (i=0;i<len2;i++)
c[1][i]=b[1][len2-i-1];
c[1][len2]='\0';
max=0;
if (len1>=len2)
max=len1;
else
max=len2;
mul();
if ((strcmp(b[1],"0")!=0) && (strcmp(b[0],"0")!=0))
{
for (i=0;i<(strlen(temp)-len1);i++)
printf(" ");
printf("%s\n",b[0]);
for (i=0;i<(strlen(temp)-len2);i++)
printf(" ");
printf("%s\n",b[1]);
for (i=0;i<strlen(temp)-max;i++)
printf(" ");
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
else if (strcmp(b[1],"0")==0)
{
printf("%s\n",b[0]);
for (i=0;i<(len1-len2);i++)
printf(" ");
printf("0\n");
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
else
{
for (i=0;i<(len2-len1);i++)
printf(" ");
printf("0\n");
printf("%s\n",b[1]);
for (i=0;i<max;i++)
printf("-");
printf("\n");
}
for (j=0;j<len2;j++)
{
if ((c[1][j]!='0')&&(atoi(c[0])!=0)&&(strlen(d)!=1))
{
for (i=0;i<len1+len2;i++)
printf("%c",c[j+2][strlen(temp)-i-1]);
printf("\n");
}
else if ((len1==1 && len2==1)&&(c[1][j]!='0')&&(atoi(c[0])!=0))
{
for (i=0;i<len1+len2;i++)
printf("%c",c[j+2][strlen(temp)-i-1]);
printf("\n");
}
}
if ((atoi(c[0])!=0) && (len1!=1 || len2!=1)&&(atoi(c[1])!=0)&&(strlen(d)!=1))
{
for (i=0;i<strlen(temp);i++)
printf("-");
printf("\n");
}
if ((atoi(c[0])!=0) && (atoi(c[1])!=0))
{
if (len1!=1||len2!=1)
{
for (i=0;i<len1+len2;i++)
printf("%c",temp[strlen(temp)-i-1]);
printf("\n");
}
}
else
{
for (i=0;i<max-1;i++)
printf(" ");
printf("0");
printf("\n");
}
printf("\n");
}
}[/c]
I solve some problem I see ...
but still WA...
PLZ......help me

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

### 338 Long Multiplication Need Help Please

[java]import java.io.IOException;
import java.util.StringTokenizer;

class Main
{
{
byte lin[]=new byte[maxLg];
int lg=0,car=-1;
try
{
while(lg<maxLg)
{
if ((car<0)||(car=='\n'))
break;
lin[lg++]+=car;
}
}
catch(IOException e)
{
return(null);
}
if ((car<0)&&(lg==0))
return(null);
return (new String (lin, 0, lg));
}
public static void main(String[] args)
{
Main newMain = new Main();
newMain.start();
}
void start()
{
String input;
StringTokenizer tokenizer;
long[][] inputs = new long[1000][2];
int count = 0;
BigInt b,c,d;
String temp;
int int_max;
int line_max;
{
tokenizer = new StringTokenizer(input);
long inp = Long.parseLong(tokenizer.nextToken());
if(tokenizer.hasMoreTokens())
{
inputs[count][0] = inp;
inputs[count][1] = Long.parseLong(tokenizer.nextToken());
count++;
}
else
{
for(int i=0;i<count;i++)
{
System.out.println();
b = new BigInt(inputs[0]);
c = new BigInt(inputs[1]);
d = b.multiply(c);
line_max = Math.max(b.Digits(),c.Digits());
int_max = Math.max(d.Digits(),line_max);
for(int j=0;j<(int_max-b.Digits());j++)
System.out.print(" ");
System.out.println(b.toString());
for(int j=0;j<(int_max-c.Digits());j++)
System.out.print(" ");
System.out.println(c.toString());

for(int j=0;j<(int_max-line_max);j++)
System.out.print(" ");

for(int j=1;j<line_max;j++)
System.out.print("-");
System.out.println("-");

if(c.lastdigit!=0&&b.lastdigit!=0)
{
for(int j=0;j<=c.lastdigit;j++)
{
temp = b.multiply((int)c.digits[j]).toString();
for(int k=0;k<(int_max-temp.length()-j);k++)
System.out.print(" ");
System.out.println(temp);
}
for(int j=1;j<int_max;j++)
System.out.print("-");
System.out.println("-");
}
if(d.Digits()<line_max)
{
for(int j=0;j<(line_max-d.Digits());j++)
System.out.print(" ");
}
System.out.println(d);
}
}
}
}
}

class BigInt implements Comparable {

int PLUS = 1;
int MINUS = -1;
int MAXDIGITS = 25;

char[] digits;
int signbit;
int lastdigit;

private BigInt() {
digits = new char[MAXDIGITS];
signbit = 1;
lastdigit = 0;
}

public BigInt(String s) {
if (s.charAt(0)=='-') {
signbit = -1;
s = s.substring(1,s.length());
} else {
signbit = 1;
}
digits = new char[MAXDIGITS];
for (int i=0; i<s.length(); i++) {
digits = (char)((int)s.charAt(s.length()-i-1)-(int)'0');
}
lastdigit = s.length()-1;
}

public BigInt(int i) {
this(""+i);
}

public BigInt(long i) {
this(""+i);
}

}

public BigInt subtract(int i) {
return subtract(new BigInt(i));
}

public BigInt multiply(int i) {
return multiply(new BigInt(i));
}

public BigInt divide(int i) {
return divide(new BigInt(i));
}

public int Digits()
{
return lastdigit+1;
}

public BigInt mod(int i) {
return mod(new BigInt(i));
}

public BigInt mod(BigInt b) {
BigInt c = divide(b);
c = c.multiply(b);
c = subtract(c);
return c;
}

BigInt c = new BigInt();
if (signbit==b.signbit) {
c.signbit = signbit;
} else {
if (signbit==MINUS) {
signbit = PLUS;
c = b.subtract(this);
signbit = MINUS;
} else {
b.signbit = PLUS;
c = subtract(b);
b.signbit = MINUS;
}
return c;
}
c.lastdigit = Math.max(lastdigit, b.lastdigit)+1;
int carry = 0;
for (int i=0; i<=c.lastdigit; i++) {
c.digits = (char) ((carry+digits+b.digits)%10);
carry = (carry+digits+b.digits)/10;
}
c.zeroJustify();
return c;
}

public BigInt subtract(BigInt b) {
BigInt c = new BigInt();
if (signbit==MINUS || b.signbit==MINUS) {
b.signbit = -1*b.signbit;
b.signbit = -1*b.signbit;
return c;
}
if (compareTo(b)<0) {
c = b.subtract(this);
c.signbit = MINUS;
return c;
}
c.lastdigit = Math.max(lastdigit,b.lastdigit);
int borrow = 0;
for (int i=0; i<=c.lastdigit; i++) {
int v = digits - borrow - b.digits;
if (digits[i] > 0) {
borrow = 0;
}
if (v<0) {
v = v+10;
borrow = 1;
}
c.digits[i] = (char)(v%10);
}
c.zeroJustify();
return c;
}

public BigInt multiply(BigInt b) {
BigInt c = new BigInt();
BigInt row = (BigInt)clone();
for (int i=0; i<=b.lastdigit; i++) {
for (int j=1; j<=b.digits[i]; j++) {
}
row.digitShift(1);
}
c.signbit = signbit*b.signbit;
c.zeroJustify();
return c;
}

public BigInt divide(BigInt b) {
BigInt c = new BigInt();
c.signbit = signbit * b.signbit;
int asignbit = signbit;
int bsignbit = b.signbit;
signbit = PLUS;
b.signbit = PLUS;
c.lastdigit = lastdigit;
BigInt row = new BigInt();
for (int i=lastdigit; i>=0; i--) {
row.digitShift(1);
row.digits[0] = digits[i];
c.digits[i] = 0;
while (row.compareTo(b)>=0) {
c.digits[i]++;
row = row.subtract(b);
}
}
signbit = asignbit;
b.signbit = b.signbit;
c.zeroJustify();
return c;
}

public boolean isZero() {
return (lastdigit==0 && digits[0]==0);
}

private void digitShift(int d) {
if (!isZero()) {
for (int i=lastdigit; i>=0; i--) {
digits[i+d] = digits[i];
}
for (int i=0; i<d; i++) {
digits[i] = 0;
}
lastdigit = lastdigit+d;
}
}

public int compareTo(Object o) {
BigInt b = (BigInt)o;
if (signbit==MINUS && b.signbit==PLUS) {
return -1;
} else if (signbit==PLUS && b.signbit==MINUS) {
return 1;
}
if (lastdigit < b.lastdigit) {
return (-1*signbit);
} else if (lastdigit > b.lastdigit) {
return signbit;
}
for (int i=lastdigit; i>=0; i--) {
if (digits[i]>b.digits[i]) {
return signbit;
} else if (digits[i]<b.digits[i]) {
return (-1*signbit);
}
}
return 0;
}

public Object clone() {
BigInt c = new BigInt();
c.signbit = signbit;
c.lastdigit = lastdigit;
for (int i=0; i<=lastdigit; i++) {
c.digits[i] = digits[i];
}
return c;
}

private void zeroJustify() {
while(lastdigit>0 && digits[lastdigit]==0) {
lastdigit--;
}
if (lastdigit==0 && digits[0]==0) {
signbit = PLUS;
}
}

public String toString() {
String s = "";
if (signbit==MINUS) {
s += "-";
}
for (int i=lastdigit; i>=0; i--) {
s += (char)('0'+digits[i]);
}
return s;
}

public static void main (String[] args) {
while (true) {
System.out.println(a+"-"+b+"="+(a.subtract(b)));
System.out.println(a+"*"+b+"="+(a.multiply(b)));
System.out.println(a+"/"+b+"="+(a.divide(b)));
System.out.println(a+"%"+b+"="+(a.mod(b)));
System.out.println();
}
}

int maxLg = 500;
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (Exception e) {
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg)).trim();
}
} [/java]

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Check here the output from Adrian Kuegel.
http://online-judge.uva.es/board/viewtopic.php?t=427

Then compare it with the output your program gives
on that same input.

There're too many differences.

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
Hm... I'm always getting OLE here! That's frustrating!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
In 95% of the cases OLE means your program
goes into an endless loop and never stops printing
to the standard output.

Hope this helps.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Test cases like

Code: Select all

001 87
002 002
Can anyone tell me the output of thiese inputs?
Thankx...
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I can't figure out your actual output, because you need to print some spaces for this problem and you have to handle them carefully. I can give you the actual output...

Output:

Code: Select all

12345
862
-----
24690
74070
98760
--------
10641390

100003
100010
------
100003
100003
-----------
10001300030

345
3455
----
1725
1725
1380
1035
-------
1191975

0
123456789
---------
0

2
324
---
8
4
6
---
648

0
234
---
0
Hope it works.
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
My program outputs:
. represents an emtpy space

Code: Select all

.1
87
--
.7
8
--
87

2
2
-
4

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi there,

I also tried many times too and received WA.
I finally found out that the error was in my multiplication algorithm.
Try to make your code as short as possible.
That way, you can find errors more easily.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

1. No there are no negative numbers;
2. There may be leading zeroes, meaning that your code should handle them.
3.

INPUT:

Code: Select all

1010 1010
OUTPUT:
. represents an emtpy space

Code: Select all

...1010
...1010
...----
..1010
1010
-------
1020100

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi HoraPe,

INPUT:

Code: Select all

1100 33
33 1100
33 101
33 100010
0
OUTPUT:
. represents an emtpy space

Code: Select all

.1100
...33
.----
.3300
3300
-----
36300

...33
.1100
.----
.33
33
-----
36300

..33
.101
.---
..33
33
----
3333

.....33
.100010
.------
....33
33
-------
3300330