10106 - Product

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

Moderator: Board moderators

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Re: 10106 product

Post by route » Wed Jan 15, 2003 5:52 pm

Yes, I can deal with zero-multiplication, and support more than 10 ^1000.
But it still gets WA.....

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jan 16, 2003 9:04 am

I think, that there are no other tricks in this problem.Try to check once again code, which generate product for this problem (multiply function I think :) )
In my opinion, if you handle correct data like 00001 * 00010, 002 * 005, 003 * 0 and can calculate numbers in given range (from problem specification) you must get Accepted :)) maybe you have problem with carry ?

Best regards
Dominik

SoLtRiX
New poster
Posts: 10
Joined: Tue Dec 03, 2002 1:17 am
Location: Portugal
Contact:

Post by SoLtRiX » Tue Apr 08, 2003 12:26 am

i didn't take care of negative numbers and i've got AC. check you calculations, maybe the error is in there.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Tue Apr 08, 2003 8:59 am

My program only deal with number less than 10^510 and got accepted.
It also doesn't handle negative number and uses simply high precision calculation.
Have you put any 0's in front of your output?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Apr 08, 2003 9:11 am

i think no tricky input there..
no -ve numbers..
so just manipulate your program using string and very simply get ac..
warning care about leading zero while working with string..
--
anupam :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

Syed Mubashshir Husain
New poster
Posts: 9
Joined: Wed Apr 02, 2003 10:28 am

Post by Syed Mubashshir Husain » Wed Apr 09, 2003 7:54 am

Take the values in string. And multiply it in string multiplication.

---
SMH

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Fri Apr 18, 2003 4:38 am

It is a very simple BigInteger type problem.
You just programmed big integer calculation carefully.
Maybe there are some mistake. Test with various numbers as possible
as you can. ( Of course, there is no negative number or floting number.
only BIG integers... ) Good luck~

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10106

Post by Riyad » Wed Aug 20, 2003 4:51 pm

hi i am having trouble with the prob 10106. i used the big integer class instead of the string multiplication . my programs deals with - ve numbers , inputs like 000001*00010,0002*00005,0003*0. but i am not at all sure about the highest limits of its . i have a question , how can can we find that powers like 10^250 will have how many digits.i used 1000000 for my inputs. will it do ?

here is my code . its too big and i am sorry for my stupidity too send too big a code.also sorry for my bad english :cry: :cry: :cry:

Code: Select all

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

const int size=100000;

/************ class starts ***************/

	int BigIntMajorVersion = 6; 
	int BigIntMinorVersion = 7; 
	int BigIntRevision = 25; 

	typedef unsigned int SizeT; 
	typedef unsigned int DATATYPE; 

	const DATATYPE BASE = 10000; 
	const DATATYPE INVALIDDATA = 65535U; 
	const SizeT LOG10BASE = 4; 
  
  
  class BigInteger 
  { 
  private: 
    DATATYPE *TheNumber; 
    SizeT Start; 
    SizeT End; 
    bool isNegative; 

    BigInteger(SizeT,DATATYPE,bool); 

    void datacopy(BigInteger const&,SizeT); 

    SizeT datalen(DATATYPE const*) const; 
    void deallocateBigInteger(); 
    void TrimZeros(); 
    void Set(DATATYPE); 

  public: 
    BigInteger(); 
    BigInteger(long); 
    BigInteger(char const*); 
    BigInteger(BigInteger const&); 

    ~BigInteger(); 

    int UnsignedCompareTo(BigInteger const&)const; 
    int CompareTo(BigInteger const&)const; 

    SizeT Digits() const; 
    bool isValidNumber() const; 
    bool isZero()const; 

    BigInteger& Add(BigInteger const&) const; 
    BigInteger& Subtract(BigInteger const&) const; 
    BigInteger& Multiply(BigInteger const&) const; 
    BigInteger& Multiply(DATATYPE const&) const; 
    BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const; 
    BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) const; 


    friend BigInteger& operator+(BigInteger const&, BigInteger const&); 
	friend BigInteger& operator-(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator*(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator*(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator*(DATATYPE const&, BigInteger const&); 
    friend BigInteger& DivideAndRemainder(BigInteger const&, BigInteger const&,BigInteger&,bool); 
    friend BigInteger& DivideAndRemainder(BigInteger const&, DATATYPE const&,DATATYPE&,bool); 
    friend BigInteger& operator/(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator/(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator/(DATATYPE const&, BigInteger const&); 
    friend BigInteger& operator%(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator%(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator%(DATATYPE const&, BigInteger const&); 

    BigInteger& operator=(BigInteger const&); 

    friend ostream& operator<<(ostream& ,  BigInteger const&); 
    friend istream& operator>>(istream& , BigInteger& ); 


    BigInteger& operator++(); 
    BigInteger& operator++(int); 

    BigInteger& operator--(); 
    BigInteger& operator--(int); 

    BigInteger& operator-(); 


    BigInteger& operator<<(SizeT); 
    BigInteger& operator>>(SizeT); 
    void abs(); 
    friend BigInteger& abs(BigInteger&); 

    int toInt(); 
    long toLong(); 

    BigInteger& Power(long )const; 
    BigInteger& SquareRoot() const; 
  }; 


int main(){
  
	char input1[size],input2[size];
	BigInteger result;
	freopen("input.in","rt",stdin);
	while(scanf("%s %s",&input1,&input2)==2){
		
		BigInteger temp1(input1),temp2(input2);
		result=temp1*temp2;
		cout<<result<<endl;
	
	
	}
  
	return 0;
  }
is there any problem with my input output format ??????????? pliz help . looking forward for help. thanx in advance.
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

bayzid
New poster
Posts: 7
Joined: Sun Sep 14, 2003 8:09 am
Location: bangladesh
Contact:

10106 WA HELP ME

Post by bayzid » Mon Nov 10, 2003 2:14 am

my code is below.every thing is ok.but judge reply wa.i m frustated.help me about this problem



/* @JUDGE_ID: xxxxxx 10106 C++ */

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
static char x[MAX],s[MAX],z[MAX];

void mul ()
{
int p,q,r,l,m,tag,u,tag1,i,t,j,k,tag2=0;
for(r=0;r<=MAX-1;r++)
z[r]='0';
tag=strlen(x)-1;
tag1=strlen(s)-1;

for(i=tag, m=0;i>=0;i--,m++)
{
for(j=tag1,k=0+m;j>=0;k++,j--)
{
l=k;
r=x-48;
q=s[j]-48;
p=r*q;

while(p!=0)
{
p=p+z[l] -48;
z[l]=(p%10)+'0';
u=p%10;
p=(p-u)/10;
l++;
}

}
}

for(i=MAX-1;i>=0;i--)
{
if(z=='0')
tag2++;
else break;
}

for(i=MAX-1-tag2;i>=0;i--)
printf("%c",z);
printf("\n");
}



void main()
{
while(scanf("%s%s",x,s)!=EOF)
{
mul();
}
}
arahman

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

10106

Post by Junayeed » Mon Jan 05, 2004 8:37 pm

I am trying this for quite a long time. But i am getting WA. I used string for multiplication. Also check if any one of the i/p is zero. Can any body help me with some i/p and o/p.

Thanks.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Jan 05, 2004 8:47 pm

Input:

4738787878
87897987
333
333
87897987
4738787878
00000000
0
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

Output:
416529915296201586
110889
416529915296201586
0
2469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135802469135308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308641975308642
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Mon Jan 05, 2004 9:05 pm

Thanks for the reply and the i/p. The last one does the trick. The last big one does not match with my o/p. Thanks. Now I have to look for the error.

Thanks

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

10106 Product

Post by cytmike » Wed May 12, 2004 3:10 am

I used a standard way to do it by using string.
But I got a TLE, how come????? :cry:

Thanks for help!!


[cpp]#include <iostream>
#include <string>

using namespace std;

int main()
{
string p,h;
while (!cin.eof())
{

cin>>p>>h;
string y;

bool sky=true;
if (p[0]=='-')
{
sky=false;
p.erase(0,1);
}
if (h[0]=='-')
{
sky=!sky;
h.erase(0,1);
}
if (p.length()<h.length())
{
y=p;
p=h;
h=y;
}

for (int l=0;l<p.length()/2;l++)
{
char i=p[l];
p[l]=p[p.length()-l-1];
p[p.length()-l-1]=i;
}
for (int l=0;l<h.length()/2;l++)
{
char i=h[l];
h[l]=h[h.length()-l-1];
h[h.length()-l-1]=i;
}

y="";
for (int k=1;k<=p.length()+h.length();k++)
y+="0";


for (int l=0;l<h.length();l++)
{
int i=0;
for (int k=0;k<p.length();k++)
{
int s=(p[k]-'0')*(h[l]-'0')+i;
i=(s+y[k+l]-48)/10;
y[k+l]=static_cast<char>((s+y[k+l]-48)%10+48);
int u=k+l;
while (i>0)
{
u++;
s=(y-'0')+i;
i=s/10;
y=static_cast<char>(s%10+48);
}
}
}

for (int l=0;l<y.length()/2;l++)
{
char i=y[l];
y[l]=y[y.length()-l-1];
y[y.length()-l-1]=i;
}
while (y[0]=='0') y.erase(0,1);

if (y=="")
cout<<"0\n";
else
{
if (!sky) cout<<'-';
cout<<y<<endl;
}
}
return 0;
}[/cpp]
Last edited by cytmike on Fri May 14, 2004 7:44 am, edited 3 times in total.

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Fri May 14, 2004 5:09 am

I really dont know why ur code
is not responding to my VC++(6) compiler
THese emotions are really problematic
is the case of brackets

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Fri May 14, 2004 7:42 am

the emotions are 8)

Post Reply

Return to “Volume 101 (10100-10199)”