338 - Long Multiplication

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

Moderator: Board moderators

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Thu Dec 21, 2006 10:42 am

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

Time that gone is gone forever ...

User avatar
kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana » Thu Dec 21, 2006 11:04 pm

thanks sakhassan!!! :D

User avatar
kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana » Sat Dec 23, 2006 9:25 pm

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

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

kintu
New poster
Posts: 6
Joined: Sun Mar 18, 2007 11:31 am
Location: In home

Post by kintu » Thu Sep 06, 2007 9:54 pm

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
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

338 Long Multiplication [wa]

Post by ishtiaq ahmed » Sun Sep 09, 2007 8:53 pm

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.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

Post by AcmNightivy » Sat Mar 22, 2008 11:24 am

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!
Last edited by AcmNightivy on Thu Jul 24, 2008 1:08 pm, edited 1 time in total.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 338 Long multiplication

Post by Sedefcho » Wed Jul 23, 2008 10:59 pm

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
New poster
Posts: 2
Joined: Wed Nov 04, 2009 7:27 am
Location: CSE-CU
Contact:

getting WA in Long Multiplicatio (338)

Post by shaon3343 » Wed Nov 04, 2009 7:50 am

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
An eye for an eye makes the whole world blind !!

Tiramisu
New poster
Posts: 8
Joined: Fri Feb 20, 2015 10:28 am

Re: 338 - Long Multiplication

Post by Tiramisu » Fri Feb 20, 2015 9:37 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 338 - Long Multiplication

Post by brianfry713 » Tue Feb 24, 2015 12:33 am

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.
Check input and AC output for thousands of problems on uDebug!

Tiramisu
New poster
Posts: 8
Joined: Fri Feb 20, 2015 10:28 am

Re: 338 - Long Multiplication

Post by Tiramisu » Tue Feb 24, 2015 2:24 am

AC :D
Last edited by Tiramisu on Thu Feb 26, 2015 9:03 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 338 - Long Multiplication

Post by brianfry713 » Tue Feb 24, 2015 9:27 pm

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.
Check input and AC output for thousands of problems on uDebug!

Tiramisu
New poster
Posts: 8
Joined: Fri Feb 20, 2015 10:28 am

Re: 338 - Long Multiplication

Post by Tiramisu » Tue Feb 24, 2015 10:06 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 338 - Long Multiplication

Post by brianfry713 » Thu Feb 26, 2015 2:00 am

Remove the // comments, submit as ANSI C, and you will get AC.
Check input and AC output for thousands of problems on uDebug!

progO
New poster
Posts: 1
Joined: Fri May 15, 2015 6:56 pm

Re: 338 - Long Multiplication

Post by progO » Fri May 15, 2015 7:01 pm

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;
}

Post Reply

Return to “Volume 3 (300-399)”