Help on FCTRL

[denny5]

Hello everybody,

I am new to SPOJ so I picked a problem I think I am good at to start, FCTRL, as I had solved this problem in paper before. I didn't find an easy way to replace printf though, so I am still using it. Not sure is it costing most of time.

From there, I am stuck for two days there.

My first try used 2 seconds. Thanks to this post here, using getchar_unlocked reduced it to 0.08 but it's still 4 times the best solution. From there, I tried different ways but can't improve.

My algorithm includes 14 times loop for 1000000000, which is the best I can think of now. Each look includes an addition and divided by 5. I think the division caused most of the time but after I changed it to this operation, it back to 0.10.

Can anybody point out which way should I go now?

Thanks.

[leppyr64]

Do you really mean this?

for 1 to 14
    for 1 to 10^9
        Do something

Surely you didn't do that on paper as well. If you've successfully done this on paper then you should be able to do this much faster

If you have more questions feel free to post them, I'm here to help.

[denny5]

Hi Leppy,

I meant 14 loops altogether. I don't think loop like yours is possible on pager. I didn't post my code here as I was not sure is that allowed. Now I think that fine.

Thanks for any advise.

Denny

#include <stdio.h>
#define getcx getchar_unlocked
#define putcx putchar_unlocked
inline void inp( int &n ) 
{
	n=0;
	int ch=getcx();
	int sign=1;
	while( ch < '0' || ch > '9' )
	{
		if(ch=='-')
			sign=-1; 
		ch=getcx();
	}
    while(  ch >= '0' && ch <= '9' )
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();

n=n*sign;
}   
inline void divu5a(int &n) {
int q, r;
q = (n >> 3) + (n >> 4);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
r = n - q*5;
n= q + (13*r >> 6);
} 
inline void divu5b(int &n) {
int q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 2;
r = n - q*5;
n=  q + (7*r >> 5);
// return q + (r>4) + (r>9);
}
inline int Z(int &num)
{
	int ret=0;
	while (num>0)
	{
		//num = num / 5;
		divu5b(num);
		ret += num;
	}
	return ret;
}
int main()
{
	int n;
	inp(n);
	for (int i=0; i<n; i++)
	{
		int num;
		inp(num); 
		printf("%d\n",Z(num)); 
	}
	return 0;
}

[leppyr64]

Oh sorry. I thought you were getting TLE. I see now that you're trying to hyper optimize. I'm not certain what can improve your code. Possibly removing variable declarations. Possibly getting rid of printf.

I don't work to this level of detail. I generally work with a "good enough" solution.