I failed this problem at a contest !

All my tests worked for b-a <= 100. I couldnt get the program work with higher numbers than 164728561229104880924. (21 digits but I need to be able to work with over 100 digits)

That's surprising, considering 164728561229104880924 requires 68 bits to be represented. How did you solve that problem without solving arbitrary length?

164728561229104880924.
This is the max. product i got from the range [134;5435435] , but i should have got a much more higher number ... my range stopped at two hundred and something... or two thousand... I cant remember exactly, but is the best i could generate.... using even an array...

Last edited on

By the way, im in the 9th grade (1st grade in Highschool, and the 1st year when i OFFICIALY study C++).
Can someone explain this algorithm to me ?

void mul(int A[], int B[])
{
      int i, j, t, C[DIGIT_NUMBER];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}

At first glance, though I could be wrong, it looks like a traditional decimal multiplication algorithm. The kind you use to multiply with pen and paper.

Ok, but can you show me how could i write it in a FULL EXECUTABLE program.
I have no idea how to do it ? should it look like :

#include<iostream>
using namespace std;
void mul(int A[100], int B[100])
{
      int i, j, t, C[10000];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[100]; i++)
      {
              for (t=0, j=1; j <= B[100] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[100]) C[100] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}
int main()
{
      mul(int A[100], int B[100]);
      return 0;
}

Last edited on

ultifinitus (1446)

haha I just did something similar to this, I was tired of not knowing exactly how many permutations would have to be done for a particular sequence, so I made an infint, I calculated (IIRC) 2^10000 (where ^ is the traditional math symbol not xor) and got

19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036
19459789933112942320912427155649134941378111759378593209632395785573004679379452676524655126605
98955205500869181933115425086084606181046855090748660896248880904898948380092539416332578506215
68309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760
73222853509164147618395638145896946389941084096053626782106462142733339403652556564953060314268
02349694003359343166514592977732796657756061725820314079941981796073782456837622800373028854872
51900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018
75783632550272832378927071037380286639303142813324140162419567169057406141965434232463880124885
61473052074319922596117962501309928602417083408076059323201612684922884962558413128440615367389
51487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920
63100418642227590867090057460641785695191145605506825125040600751984226189805923711805444478807
29063952425483392219827074044731623767608466130337787060398034131971334936546227005631699374555
08241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282
77517227365757274478411229438973381086160742325329197481312019760417828196569747589816453125843
41359598627841301281854062834766490886905210475808826158239619857701224070443305830758690393196
04603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825
74077527398634829849834075693795564663862187456949927901657210370136443313581721431179139822298
38458473344402709641828510050729277483645505786345011008529878123894739286995408343461588070439
59118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577
47592141765371568772561490458290499246102863008153558330813010198767585623434353895540917562340
08448875261626435686488335194637203772932400944562469232543504006780272738377553764067268986362
41037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389
69799688624163631337639390337345580140763674187771105538422573949911018646821969658165148513049
42223699477147630691554682176828762003627772577237813653316111968112807926694818872012986436607
68551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121
36833839359175641873385051097027161391543959099159815465441733631165693603112224993796999922678
17323580231118626445752991357581750081998392362846152498810889602322443621737716180863570154684
84058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557
15750551672751889919412971133769014991618131517154400772865057318955745092033018530484711381831
54073240533190384620840364217637039115506397890007428536721962809034779745333204683687958685802
37952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080
498190455803416826949787141316063210686391511681774304792596709376

I definitely had fun with it =]

Ha! I did it. (Well, sort of. The time limit seems a bit unreasonable. I got it down to 452 ms for the second example.)
Hint 1: The problem statement is poorly redacted. what it actually wants is the number of trailing zeroes in the representation. Thus, for 102400, the number is 2, not 3.
Hint 2: Any solution involving arbitrary precision arithmetic is too slow.

Is there a link to test it?
Can't measure the time :)
(I need to know that the approach is actually correct) No need to loop trough the numbers.

m4ster r0shi (2201)

helios wrote:
I got it down to 452 ms for the second example.

Do you count the '2's too? Do you need to?
The stream operations could be slowing you down too.

ne555 wrote:
No need to loop trough the numbers.

True.

EDIT: The best I got was 16ms without optimizations. I wonder if it can be done faster...

Last edited on

The stream operations could be slowing you down too.

std::ios_base::sync_with_stdio(false); http://codeforces.com/blog/entry/925

m4ster r0shi wrote:
The best I got was 16ms without optimizations. I wonder if it can be done faster...

What input cases? (or how many)

Edit: What should be the output if a==b? Trailing zeroes in a or in a*a?

Damn. Yesterday was Google Code Jam! T_T

Last edited on

m4ster r0shi (2201)

Here's what I did:

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

typedef unsigned long Number;

Number factor_count(Number n)
{
    Number count=0;

    while (n%5==0)
    {
        ++count;
        n/=5;
    }

    return count;
}

int main()
{
    Number a, b, i, count=0;

    ifstream fin("in.txt");
    fin >> a >> b;

    for (i=(a/5+(a%5!=0))*5; i<=b; i+=5)
        count+=factor_count(i);

    ofstream fout("out.txt");
    fout << count << endl;

    return 0;
}

ne555 wrote:
What input cases?

134 5435435

EDIT: Fixed a bug.
EDIT2: Mmm... Still doesn't work if a==b. I'll fix it later.

Last edited on

Do you count the '2's too? Do you need to?

Yes and yes.
Consider

Input:
124 125
125 125
125 126
125 128

Output:
2
0
1
3

Your output:
3
3
3
3

1
2

    for (i=(a/5+(a%5!=0))*5; i<=b; i+=5)
        count+=factor_count(i);

You don't need that loop. (also quite obfuscated, don't you think? is this the start? i= a+(a%5))

~100ms with 10000 test cases (of course, only if the approach is correct).
I based it in "calculating the number of trailing zeroes of n!"

Last edited on

Here's what I did:

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

typedef unsigned long Number;

Number factor_count(Number n)
{
    Number count=0;

    while (n%5==0)
    {
        ++count;
        n/=5;
    }

    return count;
}

int main()
{
    Number a, b, i, count=0;

    ifstream fin("in.txt");
    fin >> a >> b;

    for (i=(a/5+(a%5!=0))*5; i<=b; i+=5)
        count+=factor_count(i);

    ofstream fout("out.txt");
    fout << count << endl;

    return 0;
}

WORKING ! THANKS!

But does someone know how to check the time ? (0.1 seconds ...)

Man, I can't believe I wasted like an hour because my b was 1358821 instead of 5435435.

Immeasurably fast for b-a+1=2E+9:

#include <iostream>
#include <ctime>

int main(){
#if 0
	unsigned a=134,
		b=5435435,
#else
	unsigned a=10,
		b=10,
#endif
		zeroes=0,
		power=5,
		c=b-a+1;
	clock_t t0=clock();
	if (c==1){
		while (!(a%10)){
			zeroes++;
			a/=10;
		}
	}else{
		//2,000,000,000 == 1304400000000 (13 digits) in pental
		for (unsigned i=1;i<=13;i++,power*=5){
			zeroes+=c/power;
			unsigned mod=c%power;
			if (mod && (!(a%power) || a%power>=power-mod+1))
				zeroes++;
		}
	}
	clock_t t1=clock();
	std::cout <<zeroes<<std::endl;
	std::cout <<t1-t0<<std::endl;
	return 0;
}

PS: I find it interesting that there's two or three levels of abstraction stacked here.

Last edited on

hamsterman (4538)

Am I misunderstanding the problem here?
You have a range [a;b] where if a = 5 and b = 10, it contains 5, 6, 7, 8, 9, 10 and you need to know how may trailing 0 you get when you multiply them, right?

You need 4 divisions and 0 loops to solve this problem.
I'll write the code in a bit..

right. I was being silly..

Last edited on

int number_of_factors(int number, int factor); //how many times is factor in factorial(number)

int main(int argc, char *argv[]) {
	int l,u; 
	while( std::cin>>l>>u ){
		int fives =
			number_of_factors(u,5)
			- number_of_factors(l-1,5);
		int twos = 
			number_of_factors(u,2)
			- number_of_factors(l-1,2);
		int result = std::min(fives,twos);
		//if(u==l) result*=2;
		std::cout << result << std::endl;
	}
	return 0;
}

What do you think?