OJ Board

Posted: **Wed Jan 25, 2006 1:54 am**

Please i do not know why i got wrong answer although my answer are the same specially for 500! because some one already posted it
I test my factorial code in many other problems (factorial frequencies) and i got AC

and here are some of my ouptus

Code: Select all

0!
1
.
.
997!
403597244616453902342926527652907402110903352461393891430307973735196631901068423726375883385358710213700663198466197719394411318126551961682447808198924968051643330792790545975658652366984953410102994729193397927862707860663312211428139657339199210288839829245965893084586772188847949801354437616450752245066665598898009417557796737695167521343249479413631414534202184726421479392615730781173164526393982880263279118925406206180689438683308644696334133955184235540077242451165903811018277198321800315958279899941381566151490917379981054549852483223292752438981198080270888254399197574536460570473430371595872403169486757166154294941258045311241382930836862005052391967478429035362983199050663230586866257612402804942403442331663944341683350732204123565349869446216232111598995678724462182568501131746383857706790400107507266739002631612931124112227909672935742104968533278074796000335855930432060517447195226436187301231195091058916141499:050344865688475996490049406776931852322183786594448546457039088249340151445500357046053179773786203118550953567694888922171302000112504911516415310901200837651592219697553144378802092817085744936938401253387220705140293629858017326187150609342982365790961670958595040533106087257111984572002265443504459411577348634074285324311264856866787884661486819750191740104532976390040068195207044638407735286912244552652299854897643569096753838002459692766798724077579242119184881795985303822666475479072261654798029765478969396568888132568265390679156952788785162573969209835113890295631011123253723954647397831433613628798725785501475711681360833913542427351428039887356169177498980600730755424035095364905394044449726683195214154256679183234736759665663323909932595919590494240703808618646822069864637292815573387474665466278592062875719964916067979790641428194695892008126790265612881240871363598309598670345134414348502128648186015045295201958285280456008694206464428637204854149683653126905238350265085457726597120:5161137693595262919371358840019473383802028344531181679417716563013501242477291139042422814166369601152223293596957527530934652046662174154235850073391729650007182794396630407081318880947107940245036774649857429379220776637356890211596540009349092255988047909417594778375705723841918167663026277009033939654785671715045122185315730249393616044737902170116980736000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
998!
402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047275:25799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
999!
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504086:7375991882362772718873251977950595099527612087497546249704360141827809464649629105639388743788648733711918104582578364784997701247663288983595573543251318532395846307555740911426241747434934755342864657661166779739666882029120737914385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155861103697680135730421616874760967587134831202547858932076716913244842623613141250878020800026168315102734182797770478463586817016436502415369139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012545832716822645806652676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946595513115655203609398818061213855859:301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1000!
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Posted: **Wed Jan 25, 2006 6:07 am**

Do you solve cases until EOF is reached???, please post your main code section..., especially the input/output section to find where is your mistake..., best wishes,

Yandry.

Posted: **Thu Jan 26, 2006 3:29 pm**

here is my input and oupt code :

Code: Select all


void main()
{

	string num;

	Fact(1001);
	
	Table[0].resize(1);
	Table[0].at(0) = char(49);
	int n;
	while (cin >>n)
	{
		
		cout << n<<"!" <<endl;
		cout << Table[n] <<endl;
		
	}

	
}

In my program i made a function which creates up to the factorial of 1001 and i store them in a string array called Table.In other words if i do this

cout << Table[1000] <<endl;

i will get the factorial of 1000

Posted: **Thu Jan 26, 2006 4:43 pm**

I can't find your mistake, if you want, send me the whole source code and I will test all test cases against my AC program...

Posted: **Thu Jan 26, 2006 8:40 pm**

i have sent to you the whole source code via PM

Waiting for your reply

Posted: **Mon Mar 20, 2006 1:32 pm**

Please help me...

This is my code...

--

#include<cstdio>
#include<iostream>
using namespace std;

unsigned long int num[1005][1005];

void create()
{
int i,j,k;
for(i=1;i<=1000;i++) for(j=1;j<=1000;j++) num[j] = 0;
num[1][0] = 1;
num[1][1] = 1;
for(i=2;i<=1000;i++)
{
for(j=1;j<=num[i-1][0];j++) num[j] = num[i-1][j] * i;
for(j=1;j<=num[i-1][0];j++)
{
if(num[j]>100000)
{
num[j+1] += num[j] / 100000;
num[j] = num[j] % 100000;
}
}
if(num[j]!=0) num[0] = num[i-1][0] + 1;
else num[0] = num[i-1][0];
}
}

main()
{
int i,j,k,n;
create();
while(cin>>n)
{
cout << n << "!" << endl;
printf("%d",num[n][num[n][0]]);
for(i=num[n][0]-1;i>=1;i--) printf("%05d",num[n][i]);
cout << endl;
}
}

Posted: **Fri Mar 24, 2006 5:00 am**

I have solved the problem.
Because when n=1, the output should be 1, but I print 0.

Posted: **Wed May 24, 2006 3:38 pm**

I don't know what's wrong with my code.
The array size couldn't be large enough in my compiler.
Please help me.

Here is my source.

#include <stdio.h>
#include <string.h>
#define STR 1001
#define MAX 3000

int lena,lenb;
int a[MAX+1];
int b[MAX+1];

void proc()
{
int i,j,k,tmp,remain;
int res[MAX+1];

for(i=0 ; i<lena ; i++) res = 0;

for(i=0 ; i<lenb ; i++) {
remain = 0;
for(j=0,k=i ; j<lena ; j++) {
tmp = res[k];
res[k] = (a[j]*b + remain + tmp) % 10;
remain = (remain + tmp + a[j]*b) / 10;
k++;
}
res[k] = remain;
}

if(res[k] == 0) k--;

for(i=k ; i>-1 ; i--) {
a = res;
}

lena = k+1;

}

int main(void)
{
int i,j,run,N;
char c[STR];

int res[STR][MAX+1] = {0};

res[0][0] = 1;
res[0][MAX] = 1;

res[1][0] = 1;
res[1][MAX] = 1;

res[2][0] = 2;
res[2][MAX] = 1;

lena = 1;

a[0] = 2;

for(run=3 ; run<STR ; run++) {

sprintf(c,"%d",run);

lenb = strlen(c);

for(j=0 ; j<lenb ; j++) {
b[lenb-j-1] = c[j]-'0';
}

proc(a,b);

for(i=lena-1 ; i>-1 ; i--) {
res[run][lena-i-1] = a;
}
res[run][MAX] = lena;
}

while(scanf("%d",&N) == 1) {
printf("%d!\n",N);
for(i=0 ; i<res[N][MAX] ; i++) {
printf("%d",res[N]);
}
printf("\n");
}

return 0;
}

Posted: **Wed May 24, 2006 3:55 pm**

The array siaze may not be large enough in your compiler but UVa judge's. So when you submit your code just increase the array size.

Anyway int res[1001][3001] is large enough for this problem. But you've to declare this as either static or global.

Use code tags for posting codes.

Posted: **Thu May 25, 2006 3:08 pm**

Thanks so much , Now I've got AC.

Posted: **Sat May 27, 2006 4:49 pm**

Hello!
I have tryed to solve this problem, but without luck. The answer from the judge is always TLE, even though I use precalculation (I precalculate all factorials and store them in an array, then read the input and output the matching factorial from the array).
So my problem must be in the Big Integer multiplication method. I got Accepted to problem 10106 - Product in 0.290 with that same method, so I don't really understand why it would be TLE in this problem.

But still, I think that it could be greatly improved, so if someone could explain the proper idea behind Big Integer Multiplication I would be very grateful!

Thanx in advance!

Posted: **Mon May 29, 2006 5:35 pm**

As time reference. I used the same bigint implementation for 10106 as I did for 623.

My program solved 10106 in 0.027 while it took 2.713 to solve problem 623.

With this reference it's perhaps not surprising that your implementation resulted in a TLE.

Posted: **Mon May 29, 2006 6:17 pm**

As for the basic idea of biginteger multiplication. There are of course several methods and it all depends on how efficient you want it to be and how big numbers you have as well as what you want to use it for.

But as a basic idea, you should represent your numbers as arrays of words, where each word represent a part of the number. Each word could be an int for example. For practical reasons we need to define the max value of each word. Because we don't want the results of a multiplication to overflow an unsigned int we probably don't want the max to be more than 65535 (thus values of 65536 or above would overflow into two words). Some people would prefer to make the point of overflow 10000 instead of 65536 (simply because then it'll be quicker (and easier) to print the numbers (or convert them to strings)).

So with the last version the number 5892387 would be represented by the array {589,2387}. Because we probably also want to keep track of the sign, it might prove useful to make a struct or class for it.

We can basically use schoolbook multiplication for most problems. Thus 5892387*83220482 would be evalulated as {589,2387}*{8322,482}={589*8322,589*482+2387*8322,2387*482}. Of course we also need to take care of any carries.

If we want to multiply really big numbers (numbers with tens of thousands of digits) we might want to implement the Karatsuba algorithm http://mathworld.wolfram.com/KaratsubaM ... ation.html. It's important to realize though, that for smaller numbers (which is the case for most, if not all, problems here) karatsuba will actually be slower than schoolbook.

Posted: **Fri Jun 09, 2006 9:02 pm**

I try several times but still RE. Can someone help me >.<

Code: Select all


#include <iostream>
#include <string>
using namespace std;

int main(void){
    int b,o,z;
	int i,j,t,k,r,w;
	string a; 
	string c;
	while(cin>>z){
	a="1";


	for(o=1;o<=z;o++){
	b=o;

		a="00000"+a;
	
       
       j=0;
	   c="";
	   for(i=0;i<a.length();c+='0',i++);
	   //cout<<a<<endl;
       while(b!=0){
                   
       for(i=a.length()-1;i>=0;i--){
                    t=(b%10)*(a[i]-'0');
                    r=0;
                      
	  // cout<<" -----  "<<endl<<"           t   =   "<<t<<endl;
				
	  // cout<<a<<endl;
	
                    while(t!=0){        
        //	cout<<" c=  "<<c<<endl;	            
	 //  cout<<"  a[i-j+r]=   "<<a[i-j+r]<<endl;
	//	cout<<" c=  "<<c<<endl;		  
	 //  cout<<"  +)  t=   "<<t%10<<endl;

	           c[i-j+r]=(t%10)+c[i-j+r];
					t/=10;
                    r--;

					
                    if(c[i-j]-'0'>=10){
                                      k=c[i-j]-'0'; 
                                      w=0;
                                      c[i-j]='0';
                                      while(k!=0){
                                          c[i-j+w]+=k%10;
                                          w--;
                                          k/=10;        
                                                  } 
                                       }

					
		//cout<<" c=  "<<c<<endl;	
                                         }
                               }
                               j++;
							   b/=10;
                               }
      
    
	  
   
       
      
     
     
                               
     for(i=0;c[i]=='0';i++);  
	 a="";
	 
	 for(j=i;j<c.length();j++){
	 a=a+c[j];
	 }

	
	}




	cout<<a<<endl;
	}
    system("pause");
    return 0;
    }

Posted: **Tue Jul 04, 2006 1:06 am**

this is my code.

Code: Select all

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

class BigInteger{
public:
	string* str;
	int sign;

public:
	/*	*/
	BigInteger(string a);
	BigInteger(char* a);
	BigInteger(int i);	
	BigInteger();

	//  
	~BigInteger();


	// 
	BigInteger& operator = (const BigInteger& other);
	char& operator [](int idx);
	int size(){return str->size();}


	/*		*/
	// 
	BigInteger& operator* (BigInteger& b);
	BigInteger& operator* (int b);
	BigInteger& operator+ (BigInteger& b);
	BigInteger& operator- (BigInteger& b);



	/*	 	*/
	friend ostream &operator <<(ostream &c, const BigInteger p);
};



BigInteger::BigInteger(string a){
	if(a[0] == '-'){
		a.erase(a.begin(),a.begin()+1);
		str = new string(a);
		sign = -1;
	}
	else{
		str = new string(a);
		sign = 1;
	}
	//str = a;		
}

BigInteger::BigInteger(char* a){
	if(a[0] == '-'){
		a[0] = 0;
		str = new string(a);
		sign = -1;
	}
	else{
		str = new string(a);
		sign = 1;
	}
		
}

BigInteger::BigInteger(int i){
	char stri[10];	

	if(i >= 0){
		sprintf(stri, "%d", i);
		str = new string(stri);
	}
	else{
		i *= -1;
		sprintf(stri, "%d", i);
		str = new string(stri);
	}
}

BigInteger::BigInteger(){
	str = new string;
}

BigInteger::~BigInteger(){
		
}

BigInteger& BigInteger::operator = (const BigInteger& other){
	if(this != &other){
		*str = *other.str;
		sign = other.sign;			
	}
	return *this;
}

	/*
		*/
ostream & operator <<(ostream &c, const BigInteger p){
	bool isZero = true;

	if(p.sign == -1){
		cout << '-';
		for(int i = 0; i < p.str->size(); i++){
			if(p.str->at(i) == '0' && isZero)
				continue; 
			
			isZero = false;
			cout << p.str->at(i);
		}			
	}
	else{
		for(int i = 0; i < p.str->size(); i++){
			if(p.str->at(i) == '0' && isZero)
				continue;

			isZero = false;
			cout << p.str->at(i);
		}			
	}

	if(isZero)
		cout << 0;

	return c;
}


char& BigInteger::operator [](int idx) {
    return str->at(idx);
}



	
	/*
	
	*/
	// 
BigInteger& BigInteger::operator* (BigInteger& b){
	int i, j;
	BigInteger* newI = new BigInteger();
		
	newI->sign = sign * b.sign;

	int size1 = this->str->size();
	int size2 = b.str->size();

	for(i = 0; i < size1+size2; i++)
		newI->str->append("0");

	int num;

	int over;
	for(i = size1-1; i >= 0; i--){//. 
		over = 0;
		for(j = size2-1; j >= 0; j--){// . 
			
			num = (newI->str->at(i+j+1) - '0') + (b.str->at(j) - '0') 
				* (this->str->at(i) - '0') + over;

			newI->str->at(i+j + 1) = num%10 + '0';							
			over = num / 10;
		}
		if(over)
			newI->str->at(i+j + 1) = over + '0';
	}


	//leading 0  

	while(newI->str->at(0) == '0')
		newI->str->erase(newI->str->begin(),newI->str->begin()+1);
	
	return *newI;		
}

BigInteger& BigInteger::operator* (int i){
	char str[10];
	sprintf(str, "%d", i);

	BigInteger* b = new BigInteger(str);	

	return BigInteger::operator* (*b);
}


BigInteger& BigInteger::operator+ (BigInteger& b){
	int i, j, k;
	BigInteger* newI = new BigInteger();

	if(sign == b.sign){
		newI->sign = sign;


		int size1 = this->str->size();
		int size2 = b.str->size();
		
		int size = ((size1 > size2) ? size1 : size2);
		for(i = 0; i < size+1; i++)
			newI->str->append("0");

		int over = 0; 	
		int num1, num2, num; 
		for(i = size1-1, j = size2-1, k = size; i >= 0 || j >= 0; i--, j--, k--){
			if(i < 0)
				num1 = 0;
			else
				num1 = this->str->at(i) - '0';

			if(j < 0)
				num2 = 0;
			else
				num2 = b.str->at(j) - '0';

			num = num1 + num2 + over; 
			newI->str->at(k) = num%10 + '0';	
			over = num / 10;			
		}

		if(over)
			newI->str->at(k) = over + '0';

		//leading 0 . 
		while(newI->str->at(0) == '0')
			newI->str->erase(newI->str->begin(),newI->str->begin()+1);


		return *newI;
	}
	else{// -  

	}

			

}

BigInteger& BigInteger::operator- (BigInteger& b){
	BigInteger* newI = new BigInteger();

	return *newI;		
}



void main(){
	int n;
	
	BigInteger big[1001];

	big[0] = 0;
	big[1] = 1;

	for(int i = 2; i <= 1000; i++){
		big[i] = big[i-1] * i;		
	}

	while(cin >> n){
		cout << n << "!" << endl << big[n] << endl;
	}

	
}

I made class 'BigInteger' by myself.

and I think it works really well, with large number mutiply and addition....

I got AC with... 495, 424, 324, 10106... using this class...

anyway...
I think this problem 500!.. is relatively easy.

But i don't know why i got WA

plz, help me.

if you have any sample input, could you give me?....

OJ Board

623 - 500!

623 - 500! WA

623 WA

623

623; TLE; Explanation of Big Integer Multiplication

623 RE

623 - 500! WA