338 - Long Multiplication

Jan · Post by **Jan** » Tue Jul 26, 2005 4:57 pm

I already got it Accepted

.

Thanks daveon.

minskcity · Post by **minskcity** » Fri Dec 16, 2005 12:38 am

Is it possibe to get an accepted solution from some one? I've already got 20+ WA's.

minskcity · Post by **minskcity** » Fri Dec 16, 2005 2:51 am

Never mind, got AC.
WARNING: cout.width() does not work for this problem - I had to print the spaces manually.

Przemek D. · Post by **Przemek D.** » Mon Apr 03, 2006 11:05 pm

Hello! I am new here and I would like to say hello

I have with 338 too and I guess its the last time I am trying to solve a problem which main point is only the output look. I checked all the inputs in previous posts and threads and they seem to be allright. Can somebody give me the input for which my program generates bad output? Dont analyze the code, please

Just compile and give me the input then I will try to fix it

Thanx in advance

Code: Select all

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

typedef long long LINT;

inline int GetHowManyNums(char line[]);
inline void GetNums(char line[], LINT &a, LINT &b);
inline int GetLen(LINT number);
inline void WriteNSpaces(int howMany);
inline void WriteNHyp(int howMany);

int main()
{
    LINT a, b, result;
    int resLen, i, numMul;
    char buffer[500];
    while (cin.getline(buffer,500))
    {
        numMul = 0;
        if (GetHowManyNums(buffer) < 2)
            break;
        else
        {
            GetNums(buffer,a,b);
//            cout << a << " " << b << endl;
//            if (a == 0 && b == 0)
//                cout << 0;
//            else
            if (a == 0 || b == 0)
            {
                if (a != 0)
                    resLen = GetLen(a);
                else
                    resLen = GetLen(b);
                WriteNSpaces(resLen - GetLen(a));
                cout << a << endl;
                WriteNSpaces(resLen - GetLen(b));
                cout << b << endl;
                WriteNHyp(resLen);
                cout << endl;
                WriteNSpaces(resLen - 1);
                cout << 0;
            }
            else
            {
                result = a * b;
                resLen = GetLen(result);
                WriteNSpaces(resLen - GetLen(a));
                cout << a << endl;
                WriteNSpaces(resLen - GetLen(b));
                cout << b << endl;
                if (a > b)
                {
                    WriteNSpaces(resLen - GetLen(a));
                    WriteNHyp(GetLen(a));
                }
                else
                {
                    WriteNSpaces(resLen - GetLen(b));
                    WriteNHyp(GetLen(b));
                }
                cout << endl;
                i = 0;
                
                do
                {
                  if (b % 10 != 0)
                  {
                      if (GetLen(b) == 1 && numMul == 0)
                          cout << result;
                      else
                      {
                        WriteNSpaces(resLen - GetLen((b % 10) * a) - i);
                        cout << (b % 10) * a << endl;
                        ++numMul;
                      }
                  }
                  b = b / 10;
                  ++i;
                } while (b != 0);
                
                if (numMul != 0)
                {
                    WriteNHyp(resLen);
                    cout << endl;
                    cout << result;
                }
            }
            cout << endl;
            cout << endl;
        }
    }
    return 0;
}

inline int GetHowManyNums(char line[])
{
    int i = -1;
    int counter = 0;
    do 
    {
        ++i;
        if (int(line[i]) >=48 && int(line[i]) <= 58)//line[i] != ' ' && line[i] != '\t')
        {
            ++counter;
            do
            {
                ++i;
            } while (int(line[i]) >=48 && int(line[i]) <= 58); //line[i] != NULL && line[i] != ' ' && line[i] != 't');
        }
        
    } while (line[i] != NULL);
//    cout << counter;
    return counter;
}

inline void GetNums(char line[], LINT &a, LINT &b)
{
    int i = 0;
    do
    {
        ++i;
    } while (line[i] != NULL);

    do 
    {
        --i;
    } while (line[i] == ' ' || line [i] == NULL || line[i] == '\t');

    int pow10 = 1;
    b = 0;
    do
    {
        b = b + pow10 * (int(line[i]) - 48);
        pow10 = pow10 * 10;
        --i;
    } while (line[i] != ' ' && (line[i] == '1' || line[i] == '2' || line[i] == '3' ||
                                line[i] == '4' || line[i] == '5' || line[i] == '6' || 
                                line[i] == '7' || line[i] == '8' || line[i] == '9' ||
                                line[i] == '0') 
                            && line[i] != 't');
    
    do 
    {
        --i;
    } while (line[i] == ' ' || line[i] == '\t');
    
    pow10 = 1;
    a = 0;

    do
    {
        a = a + pow10 * (int(line[i]) - 48);
        pow10 = pow10 * 10;
        --i;
    } while (line[i] != ' ' && line[i] != '\t' && i >= 0 && (line[i] == '1' || line[i] == '2' || line[i] == '3' ||
                                                             line[i] == '4' || line[i] == '5' || line[i] == '6' || 
                                                             line[i] == '7' || line[i] == '8' || line[i] == '9' ||
                                                             line[i] == '0'));
}
               
inline int GetLen(LINT n)
{
    if (n == 0)
        return 1;
    else
    {
        int counter = 0;
        while (n != 0)
        {
            n = n / 10;
            ++counter;
        }
        return counter;
    }
}

inline void WriteNSpaces(int howMany)
{
    for (int i = 1; i <= howMany; ++i)
        cout << " ";
}

inline void WriteNHyp(int howMany)
{
    for (int i = 1; i <= howMany; ++i)
        cout << "-";
}

fpavetic · Post by **fpavetic** » Mon Apr 03, 2006 11:06 pm

hello, i am trying to solve problem 338, waing constantly but dont know why.
can someone please give output to this or any tricky case:

INPUT

Code: Select all

1023348159 962698720
1591033635 1979648441
1533525686 1107769036
1006769035 55068821
1807357916 1946018644
1003136356 566904648
1286287109 2066997517
625236461 745048768
638733758 135270077
23228126 457745641
995883267 1311720452
501743555 1605579968
1133355659 2128271149
2067799261 162455119
577567304 741171025
383924750 1150580551
1838194022 1800506810
1955245364 2018325599
1085266861 1505054497
1823240044 2063207125
0

my output:

Code: Select all

        1023348159
         962698720
        ----------
       2046696318 
      7163437113  
     8186785272   
    9210133431    
   6140088954     
  2046696318      
 6140088954       
9210133431        
------------------
985175962783656480


         1591033635
         1979648441
         ----------
         1591033635
        6364134540 
       6364134540  
     12728269080   
     6364134540    
    9546201810     
  14319302715      
 11137235445       
14319302715        
1591033635         
-------------------
3149687255106313035


         1533525686
         1107769036
         ----------
         9201154116
        4600577058 
     13801731174   
     9201154116    
   10734679802     
  10734679802      
 1533525686        
1533525686         
-------------------
1698792270861458696


       1006769035
         55068821
       ----------
       1006769035
      2013538070 
     8054152280  
    8054152280   
   6040614210    
 5033845175      
5033845175       
-----------------
55441583776757735


         1807357916
         1946018644
         ----------
         7229431664
        7229431664 
      10844147496  
     14458863328   
     1807357916    
  10844147496      
  7229431664       
16266221244        
1807357916         
-------------------
3517152200916985904


        1003136356
         566904648
        ----------
        8025090848
       4012545424 
      6018818136  
     4012545424   
   9028227204     
  6018818136      
 6018818136       
5015681780        
------------------
568682662794182688


         1286287109
         2066997517
         ----------
         9004009763
        1286287109 
       6431435545  
      9004009763   
    11576583981    
   11576583981     
   7717722654      
  7717722654       
2572574218         
-------------------
2658752260452108353


         625236461
         745048768
         ---------
        5001891688
       3751418766 
      4376655227  
     5001891688   
    2500945844    
  3126182305      
 2500945844       
4376655227        
------------------
465831654976730048


        638733758
        135270077
        ---------
       4471136306
      4471136306 
   4471136306    
  1277467516     
 3193668790      
1916201274       
638733758        
-----------------
86401564627159366


         23228126
        457745641
        ---------
         23228126
        92912504 
      139368756  
     116140630   
     92912504    
   162596882     
  162596882      
 116140630       
 92912504        
-----------------
10632573425098766


          995883267
         1311720452
         ----------
         1991766534
        4979416335 
       3983533068  
     1991766534    
    6971182869     
    995883267      
   995883267       
 2987649801        
 995883267         
-------------------
1306320449128476684


         501743555
        1605579968
        ----------
        4013948440
       3010461330 
      4515691995  
     4515691995   
    3512204885    
   2508717775     
  2508717775      
3010461330        
501743555         
------------------
805589400981106240


         1133355659
         2128271149
         ----------
        10200200931
        4533422636 
       1133355659  
      1133355659   
     7933489613    
    2266711318     
   9066845272      
  2266711318       
 1133355659        
2266711318         
-------------------
2412088150605582191


        2067799261
         162455119
        ----------
       18610193349
       2067799261 
      2067799261  
    10338996305   
   10338996305    
   8271197044     
  4135598522      
12406795566       
2067799261        
------------------
335924575013867059


         577567304
         741171025
         ---------
        2887836520
       1155134608 
      577567304   
    4042971128    
    577567304     
   577567304      
 2310269216       
4042971128        
------------------
428076150712166600


         383924750
        1150580551
        ----------
         383924750
       1919623750 
      1919623750  
    3071398000    
   1919623750     
 1919623750       
 383924750        
383924750         
------------------
441736350397537250


         1838194022
         1800506810
         ----------
        1838194022 
      14705552176  
     11029164132   
    9190970110     
14705552176        
1838194022         
-------------------
3309680854712289820


         1955245364
         2018325599
         ----------
        17597208276
       17597208276 
       9776226820  
      9776226820   
     3910490728    
    5865736092     
  15641962912      
  1955245364       
3910490728         
-------------------
3946321770487273036


         1085266861
         1505054497
         ----------
         7596868027
        9767401749 
       4341067444  
      4341067444   
     5426334305    
   5426334305      
 5426334305        
1085266861         
-------------------
1633385769593123917


         1823240044
         2063207125
         ----------
         9116200220
        3646480088 
       1823240044  
     12762680308   
    3646480088     
   5469720132      
 10939440264       
3646480088         
-------------------
3761721849366113500


        1023348159
         962698720
        ----------
       2046696318 
      7163437113  
     8186785272   
    9210133431    
   6140088954     
  2046696318      
 6140088954       
9210133431        
------------------
985175962783656480


         1591033635
         1979648441
         ----------
         1591033635
        6364134540 
       6364134540  
     12728269080   
     6364134540    
    9546201810     
  14319302715      
 11137235445       
14319302715        
1591033635         
-------------------
3149687255106313035


         1533525686
         1107769036
         ----------
         9201154116
        4600577058 
     13801731174   
     9201154116    
   10734679802     
  10734679802      
 1533525686        
1533525686         
-------------------
1698792270861458696


       1006769035
         55068821
       ----------
       1006769035
      2013538070 
     8054152280  
    8054152280   
   6040614210    
 5033845175      
5033845175       
-----------------
55441583776757735


         1807357916
         1946018644
         ----------
         7229431664
        7229431664 
      10844147496  
     14458863328   
     1807357916    
  10844147496      
  7229431664       
16266221244        
1807357916         
-------------------
3517152200916985904


        1003136356
         566904648
        ----------
        8025090848
       4012545424 
      6018818136  
     4012545424   
   9028227204     
  6018818136      
 6018818136       
5015681780        
------------------
568682662794182688


         1286287109
         2066997517
         ----------
         9004009763
        1286287109 
       6431435545  
      9004009763   
    11576583981    
   11576583981     
   7717722654      
  7717722654       
2572574218         
-------------------
2658752260452108353


         625236461
         745048768
         ---------
        5001891688
       3751418766 
      4376655227  
     5001891688   
    2500945844    
  3126182305      
 2500945844       
4376655227        
------------------
465831654976730048


        638733758
        135270077
        ---------
       4471136306
      4471136306 
   4471136306    
  1277467516     
 3193668790      
1916201274       
638733758        
-----------------
86401564627159366


         23228126
        457745641
        ---------
         23228126
        92912504 
      139368756  
     116140630   
     92912504    
   162596882     
  162596882      
 116140630       
 92912504        
-----------------
10632573425098766


          995883267
         1311720452
         ----------
         1991766534
        4979416335 
       3983533068  
     1991766534    
    6971182869     
    995883267      
   995883267       
 2987649801        
 995883267         
-------------------
1306320449128476684


         501743555
        1605579968
        ----------
        4013948440
       3010461330 
      4515691995  
     4515691995   
    3512204885    
   2508717775     
  2508717775      
3010461330        
501743555         
------------------
805589400981106240


         1133355659
         2128271149
         ----------
        10200200931
        4533422636 
       1133355659  
      1133355659   
     7933489613    
    2266711318     
   9066845272      
  2266711318       
 1133355659        
2266711318         
-------------------
2412088150605582191


        2067799261
         162455119
        ----------
       18610193349
       2067799261 
      2067799261  
    10338996305   
   10338996305    
   8271197044     
  4135598522      
12406795566       
2067799261        
------------------
335924575013867059


         577567304
         741171025
         ---------
        2887836520
       1155134608 
      577567304   
    4042971128    
    577567304     
   577567304      
 2310269216       
4042971128        
------------------
428076150712166600


         383924750
        1150580551
        ----------
         383924750
       1919623750 
      1919623750  
    3071398000    
   1919623750     
 1919623750       
 383924750        
383924750         
------------------
441736350397537250


         1838194022
         1800506810
         ----------
        1838194022 
      14705552176  
     11029164132   
    9190970110     
14705552176        
1838194022         
-------------------
3309680854712289820


         1955245364
         2018325599
         ----------
        17597208276
       17597208276 
       9776226820  
      9776226820   
     3910490728    
    5865736092     
  15641962912      
  1955245364       
3910490728         
-------------------
3946321770487273036


         1085266861
         1505054497
         ----------
         7596868027
        9767401749 
       4341067444  
      4341067444   
     5426334305    
   5426334305      
 5426334305        
1085266861         
-------------------
1633385769593123917


         1823240044
         2063207125
         ----------
         9116200220
        3646480088 
       1823240044  
     12762680308   
    3646480088     
   5469720132      
 10939440264       
3646480088         
-------------------
3761721849366113500

and here is my code:

Code: Select all

acc

thanks

fpavetic · Post by **fpavetic** » Thu Apr 06, 2006 8:16 pm

is my way of taking the input correct?

fpavetic · Post by **fpavetic** » Thu Apr 06, 2006 8:22 pm

the output up there is correct. i just made a silly mistake

IRA · Post by **IRA** » Thu Jul 13, 2006 7:08 am

I don't know why OLE?
Who can help me?
Thanks in advance!

Code: Select all

#include <cstdio>
#include <iostream.h>

long long max(long long a,long long b)
{
	if(a>b)
		return a;
	return b;
}

void printPa(char ch,int len)
{
	while(len--)
        cout<<ch;
		//printf("%c",ch);
}

int getLen(long long val)
{
	int len=0;
	if(val==0)
		return 1;
	while(val)
	{
		len++;
		val=val/10;
	}
	return len;
}

void process(long long x,long long y)
{
	int mLen,b,cLen,step,f;
	int xy_Len,xLen,yLen;
    long long temp,h;

	mLen=max(cLen=max(xLen=getLen(x),yLen=getLen(y)),xy_Len=getLen(x*y));

	printPa(' ',mLen-xLen);
	cout<<x<<endl;
    //printf("%lld\n",x);
	printPa(' ',mLen-yLen);
	cout<<y<<endl;
    //printf("%lld\n",y);
	printPa(' ',mLen-cLen);
	printPa('-',cLen);
		temp=y;
		step=0;
		f=0;

		while(temp)
		{
			h=(x*(temp%10));
			if(h!=0)
				f++;
			temp=temp/10;
		}
		if(f!=1&&f!=0)
		{
		temp=y;
		while(temp)
		{
			h=(x*(temp%10));
			if(h!=0)
			{
                cout<<"\n";
				//printf("\n");
				printPa(' ',mLen-getLen(h)-step);
				cout<<h;
                //printf("%lld",h);
			}
			temp=temp/10;
			step++;
		}
		}
	
		if(f==1||f==0)
		{
				//printf("\n");
				cout<<"\n";
				printPa(' ',mLen-xy_Len);
				//printf("%lld\n",x*y);
				cout<<x*y<<endl;
		}else{
				//printf("\n");
				cout<<"\n";
				printPa('-',mLen);
				printf("\n");
				printPa(' ',mLen-xy_Len);
				//printf("%lld\n",x*y);
				cout<<x*y<<endl;
		}
}

int  main()
{
	char sen[1000];
	long long x=1100,y=1100;
	while( gets(sen) )
	{
		if( sscanf(sen,"%lld %lld",&x,&y)!=2 )
			break;
		process(x,y);
		printf("\n");
	}
	return 0;
}

IRA · Post by **IRA** » Thu Jul 13, 2006 9:43 am

I have know my mistake....
long long is only 19 digits....isn't enough!

sane · Post by **sane** » Sun Aug 20, 2006 6:17 pm

Hi all,

Im continuously getting wrong anwer.. lots of submissions

...

Im handling leading zeros, omiting intermediate results whose value is zero.. printing hypens according to the specification.. I cant understand what is the problem..
Im jus got into this and dont know much..Can anybody tell me the mistake??..plus
what is the criteria of printing spaces before the each output line??
Here is my teminatin code-->
do{
if(scanf("%s%s",a,b) < 2)
break;
// code
}while(!feof(stdin));

is it right?..

Thanks

sakhassan · Post by **sakhassan** » Tue Nov 21, 2006 5:43 pm

getting OLE !!!!!!!!I dont know what's the problem this is ma code

Code: Select all


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

#define N 20

void rev(char from[N], char to[N])
{
	int len;
	int i;

	len = strlen(from);
	for(i=0;i<len;i++)
		to[i] = from[len-1-i];
	to[i]='\0';
}

void mul(char res[N], char a[N],int n)
{


	int len;
	int i,j;
	int carry;
	int sum;

	char temp[N];

	len = strlen(a);
	carry = 0;

	for(j=0,i=len-1;i>=0;i--)
	{
		sum = ( a[i] - '0')*n + carry;

		if(sum>=10)
		{
			carry = sum/10;
			sum%=10;
		}
		else
			carry = 0;

		temp[j++] = sum + '0';


	}
	if(carry)
	{
		while(carry)
		{
			temp[j++] = (carry%10) + '0';
			carry/=10;
		}
	}


	//temp[j]='\0';
	//rev(temp,res);

	len = j-1;
	for(i=0;len>=0;len--,i++)
	{
		res[i] = temp[len];
	}
	res[i]='\0';



//	return res;

}




void sum(char res[N],char a[N], char b[N])
{

	int len1,len2;
	char str1[N],str2[N];
	int i;
	int rem;
	int sum;
	char temp[N];


	len1 = strlen(a);
	len2 = strlen(b);

	rev(a,str1);
	rev(b,str2);

	rem = 0;
	for(i=0;(i<len1 && i<len2); i++)
	{
		sum = (str1[i]-'0') + (str2[i]-'0') + rem;
		temp[i] = sum%10 + '0';
		rem = sum/10;
	}

	for(;i<len1; i++)
	{
		sum = (str1[i]-'0') + rem;
		temp[i] = sum%10 + '0';
		rem = sum/10;
	}

	for(;i<len2; i++)
	{
		sum = (str2[i]-'0') + rem;
		temp[i] = sum%10 + '0';
		rem = sum/10;
	}


	if(rem!=0) temp[i++]= rem +'0';
	temp[i]='\0';
	if(strlen(temp)==0)
		strcpy(temp,"0");
	rev(temp,res);

}


int main()
{
   char str[N],str1[N],str2[N];
   char arr[N][N];
   int i,j;
   char ans[N];
   char temp1[N],temp2[N];
   int num,count;
   int desh1,desh2;

   //freopen("338.cpp","w",stdout);

   while(1)
   {

	gets(str);
	if(strcmp(str,"0")==0)
	 break;

	sscanf(str,"%s%s",str1,str2);
	//scanf("%s",str2);

	memset(arr,'\0',sizeof(arr));


	count = strlen(str2);


	for(j=0,i=count-1;i>=0;i--,j++)
	{
	       num = str2[i]-'0';
	       mul(arr[j],str1,num);

	}

	strcpy(ans,"");
	strcpy(ans,arr[0]);
	for(i=1;i<count;i++)
	{
	     strcpy(temp1,"");
	     strcpy(temp2,"");
	     mul(temp2,arr[i],pow(10,i));
	     sum(temp1,ans,temp2);
	     strcpy(ans,temp1);

	}

	desh1 = strlen(str1)>strlen(str2)?strlen(str1):strlen(str2);
	desh2 = strlen(ans);

	if(strcmp(ans,"0")==0)
	{


		for(i=0;i<desh1-strlen(str1);i++)
		 printf(" ");
		printf("%s\n",str1);
		for(i=0;i<desh1-strlen(str2);i++)
		 printf(" ");
		printf("%s\n",str2);

		for(i=0;i<desh1;i++)
		 printf("-");
		printf("\n");
		for(i=0;i<desh1-1;i++)
		printf(" ");
		printf("0\n");
		continue;

	}


	for(i=0;i<desh2-strlen(str1);i++)
		printf(" ");
	printf("%s\n",str1);

	for(i=0;i<desh2-strlen(str2);i++)
		printf(" ");
	printf("%s\n",str2);


	for(i=0;i<desh2-desh1;i++)
		printf(" ");
	for(i=0;i<desh1;i++)
	 printf("-");

	printf("\n");

	if(count>1)
	 for(i=0;i<count;i++)
	 {
	     for(j=0;j<desh2-strlen(arr[i])-i;j++)
		printf(" ");

		printf("%s\n",arr[i]);
	 }


	if(count>1)
	{
	   for(i=0;i<desh2;i++)printf("-");
		printf("\n");
	}
	printf("%s\n",ans);
	printf("\n");

   }


   return 0;
}

Jan · Post by **Jan** » Wed Nov 22, 2006 6:52 am

Try the samples...

Input:

Code: Select all

0 0
1234567890 0
0 1234567890
1234567890 1234567890
0

Output:

Code: Select all

0
0
-
0

1234567890
         0
----------
         0

         0
1234567890
----------
         0

         1234567890
         1234567890
         ----------
       11111111010
       9876543120
      8641975230
     7407407340
    6172839450
   4938271560
  3703703670
 2469135780
1234567890
-------------------
1524157875019052100

Hope these help. Its really hard to get this one accepted.

sakhassan · Post by **sakhassan** » Wed Nov 22, 2006 11:49 am

Is there any test case like
9999999999 9999999999
if so whats the output ???

Thanks in advance

Jan · Post by **Jan** » Wed Nov 22, 2006 5:04 pm

Here are some more...

Input:

Code: Select all

9999999999 9999999999
111 9
111 99
9999999999 1
1 9999999999
5555555555 2222222222
0

Output:

Code: Select all

          9999999999
          9999999999
          ----------
         89999999991
        89999999991
       89999999991
      89999999991
     89999999991
    89999999991
   89999999991
  89999999991
 89999999991
89999999991
--------------------
99999999980000000001

111
  9
---
999

  111
   99
  ---
  999
 999
-----
10989

9999999999
         1
----------
9999999999

         1
9999999999
----------
         9
        9
       9
      9
     9
    9
   9
  9
 9
9
----------
9999999999

          5555555555
          2222222222
          ----------
         11111111110
        11111111110
       11111111110
      11111111110
     11111111110
    11111111110
   11111111110
  11111111110
 11111111110
11111111110
--------------------
12345679009876543210

Hope these help.

sakhassan · Post by **sakhassan** » Wed Nov 22, 2006 8:27 pm

At Last I got AC

Thanks for the Test cases J@N ...... I handled those cases .... But I forgot this one

200 200

output :
..200
..200
-----
40000

My mistake !!!!

OJ Board

338 - Long Multiplication

need hlp :)

338 - long multiplication

338 OLE

338: WA not understandable