338 - Long Multiplication

[sakhassan]

Kana pls Check the following inputs

01 01
0 00
020 12

Code: Select all

ur output is :

 01
 01
 --
 01
---
001

 0
00
--
 0

 020
  12
 ---
 040
020
----
0240

Code: Select all

This is my output:

1
1
-
1

0
0
-
0

 20
 12
 --
 40
20
---
240

[kana]

thanks sakhassan!!!

[kana]

i have no idea ehy i'm getting WA...WA...WA.... plz help.....

can anyone give me some critical i/o....

[kintu]

i am tired getting WA. I have tested all the input of forum. Everything ok. But why WA in uva???
give my sample input & output or test my code

Code: Select all

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

int multiply(long long first, char *sec, char *ans)
{
	long long carry,m;
	int len,i;
	char *p,*r,*q;
	p=sec;
	r=ans;
	carry=0;
	while(*p)
	{
		m=first*(*p-48)+carry;
		*r=m%10+48;
		carry=m/10;
		r++; p++;
	}
	while(carry)
	{
		*r=carry%10+48;
		carry=carry/10;
		r++;
	}
	*r='\0';
	r--;
	q=ans;
	len=strlen(ans);
	for(i=0;i<len/2;i++)
	{
		*q=*r+*q;
		*r=*q-*r;
		*q=*q-*r;
		r--;q++;
	}
	return len;

}


main()
{
//   freopen("input.txt","rt",stdin);
//    freopen("out.txt","wt",stdout);

	long long a,b,temp;
	int i,len_ans,len_b,len_a,max,pens;
	char sec[100],ans[100];

	while(scanf("%lld %lld",&a,&b)==2)
	{
		i=0;
		temp=b;
		while(temp)
		{
			sec[i++]=temp%10+48;
			temp/=10;			
		}
		sec[i]='\0';
		len_b=i;
		len_ans=multiply(a,sec,ans);

		len_a=0;
		temp=a;
		while(temp)
		{
			len_a++;
			temp/=10;
		}
		if(len_a==0)
			len_a=1;
		if(len_a>=len_b)
			max=len_a;
		else
			max=len_b;
		if(max>len_ans)
			pens=max;
		else
			pens=len_ans;
		printf("%*lld\n",pens,a);
		printf("%*lld\n",pens,b);

		for(i=0;i<(len_ans-max);i++)
			printf(" ");
		for(i=0;i<max;i++)
			printf("-");
		printf("\n");
		if(a==0)
			printf("%*lld\n",max,a);
		else if(b==0)
			printf("%*lld\n",max,b);
		else
		{

		max=len_ans;
		for(i=0;i<len_b;i++)
		{
			if(a*(sec[i]-48))
				printf("%*lld\n",max,a*(sec[i]-48));
			max--;
		}

	  if(len_b!=1)
	  {
		for(i=0;i<len_ans;i++)
			printf("-");
		printf("\n%s\n",ans);
	  }
		}

	  printf("\n");

	}

return 0;
}

[ishtiaq ahmed]

This problem derives me completely mad. Could you give me some sample input output ? I have tested all the inputs from forum. it seems to be okay. Where is the problem? Here is my code

Code: Select all

///			 Long Multiplication  338


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

char  xx[11] , yy[11] , result[20][20] , final[21];
int length_xx , length_yy , length_final ;


void processing(  int sign )
{
	int length , i , flag = 0;
	char temp , str[11] ;
	if( !sign )
		strcpy( str , xx ) ;
	else 
		strcpy( str , yy ) ;
	length = strlen( str ) ;
	for(i = 0 ; i < length/2 ; i ++)
	{
		temp = str[i] ;
		str[i] = str[length - i - 1 ] ;
		str[length - i - 1 ] = temp ;
	}
	for(i= length - 1 ; i >= 0 ; i--)
	{
		if(str[i] != '0')
		{
			flag = 1 ;
			break ;
		}
	}
	if(flag )
		str[i + 1] = NULL ;
	else
		str[1] = NULL ;
	if( !sign)
	{
		strcpy( xx , str ) ;
		length_xx = strlen( xx ) ;
	}
	else
	{
		strcpy( yy , str ) ;
		length_yy = strlen( yy ) ;
	}
}


void multiplication( void )
{
	int i = 0 , flag , j , k= -1, carry = 0 , carry_result , temp ,sign = -1 , temp_result ;
	for(i=0;i < 21 ; i++)
		final[i] = '0' ;
	for(j = 0 ; j < length_yy ; j++)
	{
		sign ++ ;
		k = sign - 1 ;
		carry_result = 0 ;
		carry = 0 ;
		flag = 0 ;
		for(i = 0 ; i < length_xx ; i++)
		{
			k++ ;
			temp = (( xx[i] - '0' ) * ( yy[j] - '0' )) + carry + final[k] - '0';
			temp_result = (( xx[i] - '0' ) * ( yy[j] - '0' )) + carry_result ;
			final[k] = ( temp % 10 ) + '0';
			carry = temp / 10;
			carry_result = temp_result / 10 ;
			result[j][i] = ( temp_result % 10 ) + '0' ; 
		}
		if(i == length_xx && carry > 0)
		{
			final[++k] = (carry % 10) + '0';
			carry /= 10 ;
			if(carry)
				final[++k] = carry + '0' ;
			carry = 0 ;
		}
		if(i == length_xx && carry_result > 0)
		{
			flag = 1 ;
				result[j][i] = ( carry_result % 10 ) + '0' ; 
			carry_result /= 10 ;
			if(carry_result)
				result[j][++i] = carry_result + '0' ;
			result[j][++i] = '\n' ;
			carry_result = 0 ;
		}
		if( !flag )
			result[j][i] = '\n' ;
	}
	final[++k] = NULL ;
	length_final = strlen( final) ;
}


void reverse( char str[] , int length)
{
	int i ;
	char tempo ;
	for(i= 0 ; i< length/2 ;i++)
	{
		tempo = str[i] ;
		str[i] = str[length - 1 - i] ;
		str[length - 1 - i] = tempo ;
	}
}


void final_processing( void )
{
	int count = 0 , i ;
	for(i= length_final - 1 ; i >= 0 ; i--)
		if(final[i] == '0')
			count ++ ;
	if(count == length_final)
	{
		final[1] = NULL ;
		length_final = 1 ;
	}
}
void display( void )
{
	int max ,hifen ,space , i , j , temp , printable , symbol;
	hifen = (length_xx >= length_yy) ? length_xx : length_yy ;
	max = (length_final >= hifen) ? length_final : hifen ;
	space = max - hifen ;
	for(j= 0 ; j < max - length_xx ; j++)
		printf(" ");
	puts( xx ) ; 
	for(j= 0 ; j< max - length_yy ; j++)
		printf(" ");
	puts( yy ) ; 
	for(j= 0 ; j< space ; j++)
		printf(" ");
	for(i= 0 ; i < hifen ; i++)
		printf( "-" ) ; 
	printf("\n");
	i= 0 ;
	while( i < length_yy  && length_xx > 1 && length_yy > 1)
	{
		temp = 0 ; symbol = 0 ;
		for(j=0; result[i][j] != '\n' ; j++)
		{
			temp++;
			if(result[i][j] == '0')
				symbol ++ ;
		}
		if(symbol != temp )
		{
			printable = max - temp - i ;
			for( j= 0; j < printable ; j++)
				printf(" ");
			for( j= temp-1; j>=0 ; j--)
				printf("%c",result[i][j]);
			printf("\n");
		}
		i++ ;
	}
	if( length_xx > 1 && length_yy > 1 )
	{
		for( i=0 ; i < max ; i++ )
			printf("-");
		puts("");
	}
	for(i= 0 ; i < max - length_final ; i++)
		printf(" ");
	puts(final);
	puts("");
}
int main()
{
//	freopen("c:\\input.txt","r",stdin);
//	freopen("c:\\out.txt","w",stdout);
	while(scanf("%s%s", xx , yy ) == 2 )
	{
		processing( 0 ) ;
		processing( 1 ) ;
		multiplication();
		reverse( xx , length_xx ) ;
		reverse( yy , length_yy ) ;
		reverse( final , length_final ) ;
		final_processing() ;
		display() ;
		
	}



	return 0 ;
}

waiting for your reply.

[AcmNightivy]

Why I always got PE??I printed a extra blank line at last and got PE, as well as delete it~~WHY???
Here is the code~

Code: Select all

ACC..Sedefcho~Thanks~Really!

[Sedefcho]

You have PE because of two things.

1) you print two empty lines instead of one after some test cases.
2) you don't print new line char after the last case, although most
problems here ask for 'blank line between consecutive test cases'
their outputs on the judge actually require you to print an additional
new line char after the last test case.

I ran your program and it prints what I have posted below.
There you can see that you have 2 separator lines instead of just 1 (one)
between the outputs of the two consecutive test cases.

Code: Select all

   2520
   2000
   ----
5040000


 1245
    9
 ----
11205

Hope this helps you.
Don't pay attention to the second test case output.
It looks a little bit distorted.

Below is the input file I used to run your program.

Code: Select all

9000900009 9000900009
9999999999 2000000200
   4 7
0 0
0 1
10000 1000010000
3000 1234
135  46
    12345   862
0 123456789
1100 1100
1020 1020
2520 2000
1245 9
9 12345
0

You can be happy though because my current program prints the
same as yours on my sample input (without the additional empty
separator lines which you print) but gets WA

[shaon3343]

hi there,
I'm a novice programmer. I'm getting WA in the problem no.338 (Long Multiplication) . Can anyone give me some critical input for this problem?
Please help me.
shaon

[Tiramisu]

I am getting PE. can anyone tell me why??? between two outputs there should be a blank line, what about the last one? here's some input output from my code:

input

Code: Select all

123456  4324
  12234  909
454609 45606
234 0
 0  3434
234 657567
345 200
200    345
0

output

Code: Select all

   123456
     4324
   ------
   493824
  246912
 370368
493824
---------
533823744

   12234
     909
   -----
  110106
110106
--------
11120706

     454609
      45606
     ------
    2727654
  2727654
 2273045
1818436
-----------
20732898054

234
  0
---
  0

   0
3434
----
   0

      234
   657567
   ------
     1638
    1404
   1170
  1638
 1170
1404
---------
153870678

  345
  200
  ---
69000

  200
  345
  ---
 1000
 800
600
-----
69000

[brianfry713]

You can generate output at:
http://www.udebug.com/UVa/338

Follow the output for each multiplication by a blank line, including the last one.

You can post your code if you want.

[Tiramisu]

AC

[brianfry713]

That code won't compile.
If you want to use ANSI C, then you can't use C++ comments //
If you want to use C++ or C++11 (and you should), don't use new as a variable name.

[Tiramisu]

got your point. but when I submitted my code, I actually removed those two comments. I was not sure about where to print a newline, I tried different combinations, got PE for all of those(not WA!!). So i guess there is something I am missing. i am a novice programmer, so it just can be a very silly mistake

[brianfry713]

Remove the // comments, submit as ANSI C, and you will get AC.

[progO]

I've tried all the input cases of this forum... still getting wa... what am I doing wrong....

here's my code...

Code: Select all

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

int carry = 0;

string convToStr(long long val) {
    if(val == 0) return string("0");

    string out;

    while(val != 0) {
        int a = val % 10;
        out = ((char)(a + '0')) + out;

        val /= 10;
    }

    return out;
}

string sumUp(vector<string>::iterator itStart, vector<string>::iterator itEnd) {
    int colSum = 0;
    int quot = 0;
    carry = 0;
    vector<string>::iterator it;
    string resStr;

    int len = itStart->length() - 1;

    for(int i = len; i >= 0; i--) {
        colSum = 0;
        quot = 0;

        it = itStart;
        while(it != itEnd) {
            if((*it)[i] != ' ') {
                colSum += (((*it)[i]) - '0');
            }
            it++;
        }

        colSum += carry;
        quot = colSum % 10;
        carry = (colSum / 10);

        resStr = ((char)(quot + '0')) + resStr;
    }
    if(carry != 0) {
        resStr = ((char)(carry + '0')) + resStr;
    }

    return resStr;
}

vector<string> getTheOutputs(const string& str1, const string& str2) {
    vector<string> reses;
    long long num = atoll(str1.c_str());
    int q = 0;

    for(int i = str2.length() - 1; i >=0 ; i--) {
        int mul = str2[i] - '0';

        long long res = num * mul;
        string aq = convToStr(res);

        if(aq != "0") {
            for(int n = 0; n < q; n++) {
                aq = aq + " ";
            }
            reses.push_back(aq);
        }

        q++;
    }

    return reses;
}

void addSpaces(vector<string>& vec) {
    int spaceCount = vec[vec.size() - 1].length();
    int diff = 0;

    for(int i = 0; i < vec.size() - 1; i++) {
        diff = spaceCount - vec[i].length();

        for(int j = 0; j < diff; j++) {
            vec[i] = " " + vec[i];
        }
    }
}

int main() {
    string inp;
    string str1;
    string str2;
    char x[20];
    char y[20];

    bool leadNewLine = false;

    while(scanf("%s %s", x, y) == 2) {
        str1 = string(x);
        str2 = string(y);

        if(leadNewLine) {
            cout << endl;
        }
        else {
            leadNewLine = true;
        }

        //stringstream strStrm(inp);
        vector<string> outs;
        vector<string> finRes;

        /*strStrm >> str1;
        strStrm >> str2;*/

        long long a = atoll(str1.c_str());
        long long b = atoll(str2.c_str());

        if(str1 == "0" || str2 == "0") {
            str1 = convToStr(a);
            str2 = convToStr(b);

            int len = max(str1.length(), str2.length());
            int diff = len - str1.length();
            for(int i = 0; i < diff; i++) {
                str1 = " " + str1;
            }

            diff = len - str2.length();
            for(int i = 0; i < diff; i++) {
                str2 = " " + str2;
            }

            finRes.push_back(str1);
            finRes.push_back(str2);

            addSpaces(finRes);

            string line;
            for(int i = 0; i < len; i++) {
                line += "-";
            }
            finRes.push_back(line);

            line = "0";
            diff = len - line.length();
            for(int i = 0; i < diff; i++) {
                line = " " + line;
            }
            finRes.push_back(line);
        }
        else {
            finRes.push_back(convToStr(a));
            finRes.push_back(convToStr(b));

            int len = max(finRes[0].length(), finRes[1].length());
            string line;
            for(int i = 0; i < len; i++) {
                line += "-";
            }
            finRes.push_back(line);

            outs = getTheOutputs(str1, str2);

            if(outs.size() < 2) {
                finRes.push_back(convToStr(a * b));

                addSpaces(finRes);
            }
            else {
                finRes.insert(finRes.end(), outs.begin(), outs.end());

                addSpaces(finRes);
                string q = sumUp(finRes.begin() + 3, finRes.end());
                finRes.push_back(q);

                len = finRes[finRes.size() - 1].length();
                line = "";
                for(int i = 0; i < len; i++) {
                    line += "-";
                }

                finRes.insert(finRes.end() - 1, line);

                if(carry) {
                    for(int i = 0; i < finRes.size() - 2; i++) {
                        finRes[i] = " " + finRes[i];
                    }
                }
            }
        }

        for(int i = 0; i < finRes.size(); i++) {
            finRes[i].erase(find_if(finRes[i].rbegin(), finRes[i].rend(), bind1st(not_equal_to<char>(), ' ')).base(), finRes[i].end());
            cout << finRes[i] << endl;
        }
    }

    return 0;
}