623 - 500!

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

Moderator: Board moderators

Post Reply
boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

623 - 500! WA

Post by boshkash1986 » 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


neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » 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.

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » 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

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » 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... :o

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Thu Jan 26, 2006 8:40 pm

i have sent to you the whole source code via PM

Waiting for your reply

lyh91208
New poster
Posts: 4
Joined: Mon Mar 20, 2006 1:26 pm
Location: Taipei

623 WA

Post by lyh91208 » 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;
}
}

lyh91208
New poster
Posts: 4
Joined: Mon Mar 20, 2006 1:26 pm
Location: Taipei

Post by lyh91208 » 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.

xivphoenix
New poster
Posts: 3
Joined: Wed May 24, 2006 3:29 pm
Location: Thailand

623

Post by xivphoenix » 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;
}

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » 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.

xivphoenix
New poster
Posts: 3
Joined: Wed May 24, 2006 3:29 pm
Location: Thailand

Post by xivphoenix » Thu May 25, 2006 3:08 pm

Thanks so much , Now I've got AC. :D

Qodeus
New poster
Posts: 6
Joined: Mon Mar 06, 2006 10:32 pm

623; TLE; Explanation of Big Integer Multiplication

Post by Qodeus » 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! :)

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » 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.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » 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.

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

623 RE

Post by thomas1016 » 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;
    }


bidol
New poster
Posts: 7
Joined: Sun Jul 10, 2005 1:14 pm

623 - 500! WA

Post by bidol » 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?....
sorry, i'm not good at english.

Post Reply

Return to “Volume 6 (600-699)”