338 - Long Multiplication

[angga888]

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]

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]

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?

[Ianchen]

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

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]

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

class Main
{
static String ReadLn(int maxLg)
{
byte lin[]=new byte[maxLg];
int lg=0,car=-1;
try
{
while(lg<maxLg)
{
car=System.in.read();
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;
while ((input=Main.ReadLn (255))!=null)
{
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 add(int i) {
return add(new BigInt(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;
}

public BigInt add(BigInt b) {
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;
c = add(b);
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++) {
c = c.add(row);
}
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) {
BigInt a = new BigInt(readLine());
BigInt b = new BigInt(readLine());
System.out.println(a+"+"+b+"="+(a.add(b)));
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();
}
}

static String readLine () {
int maxLg = 500;
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
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]

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]

Hm... I'm always getting OLE here! That's frustrating!

[Sedefcho]

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]

Is there any leading zeroes??

Test cases like

Code: Select all

001 87
002 002

Can anyone tell me the output of thiese inputs?
Thankx...

[Jan]

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.

[daveon]

My program outputs:
. represents an emtpy space

Code: Select all

.1
87
--
.7
8
--
87

2
2
-
4

[daveon]

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]

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]

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