11029 - Leading and Trailing
Moderator: Board moderators
11029 - Leading and Trailing
how to get the first tree digits? Can this be done in O(logn), i mean, is it realted with modular exponentiation?
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Last edited by helloneo on Sat May 13, 2006 8:31 pm, edited 1 time in total.
Try to replace your part:
with this:
Code: Select all
temp1 = temp1 - temp2 + 4.0;
temp3 = pow(10.0, temp1);
sprintf(buf1, "%.0Lf", temp3);
Code: Select all
temp1 = temp1 - temp2;
temp3 = pow(10.0, temp1);
while (temp3<1000.0) temp3 *= 10.0;
int tmp = floor(temp3);
while (tmp>999) tmp /= 10;
sprintf(buf1, "%d", tmp);
I don't think so, all of yours are right.
I think the bug of helloneo's code is in finding last three digits.
Did you know logarithm of finding n^k algorithm?
If you have no idea, you could reference it in Intro. to Algorithm.
Similar idea in UVa374, if you solved this problem.
You could use same thought to solve logarithm of it.
Hope this helps.
Lonely ^^
I think the bug of helloneo's code is in finding last three digits.
Did you know logarithm of finding n^k algorithm?
If you have no idea, you could reference it in Intro. to Algorithm.
Similar idea in UVa374, if you solved this problem.
You could use same thought to solve logarithm of it.
Hope this helps.
Lonely ^^
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Last edited by jan_holmes on Sun May 14, 2006 7:34 am, edited 3 times in total.
It's because of overflow
Replace
with
or
in the main program use
instead of
Replace
Code: Select all
return (pangkat(search(a,b/2))%1000*a%1000)%1000;
Code: Select all
return (pangkat(search(a,b/2))%1000*(a%1000))%1000;
in the main program use
Code: Select all
search(a%1000,b)
Code: Select all
search(a,b)
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Hello..~
I got WA with that code too..
Don't know why it doesn't work.. possibly precision error..
Replace that part with what kp suggested.. ~
Last edited by helloneo on Sun May 14, 2006 7:50 am, edited 1 time in total.
Code: Select all
temp1 = temp1-temp2+4.0;