| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:Who solved it in mathematical way?In Reply To:Re:Who solved it in mathematical way? Posted by:g33k at 2011-03-12 14:29:58 >
> I think using the `stupid' solution can be accepted is because of the precision lost of floats. The answers were calculated in this stupid way.
>
> But mathematical way won't cause precision lost. So their answers are different.
I think you have made the following mistakes:
a) printf("%.0lf card(s)\n",--n);
//Since you are printing float, you could have got answer(s) which are different from what Online Judge is expecting.
b) I also did the mathematical way. But you need to take some precautions.
http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29
(This gives the mathematical formula)
Let's define:
i)
sum_k = 0
for j in range(1,k+1):
sum_k += 1.0/j
ii) Mathematical sum:
sum_k_eqn = log(k) + gamma + 1.0/(2*k)
//gamma = 0.5772
Note: The 3rd term is ~1.0/(2*k) // Its approx not exact.
For some k, the sum based on the two methods (rounded to 2 decimal pts) are different.
The following python code prints those cases for the sum range mentioned in the problem.
>>> for k in range(1,281):
sum_k = 0
for j in range(1,k+1):
sum_k += 1.0/j
sum_k_eqn = log(k) + gamma + 1.0/(2*k)
if ( int(sum_k*100+0.5)*1.0/100 != int(sum_k_eqn*100+0.5)*1.0/100 ):
diff_after_rounded = int(sum_k_eqn*100 + 0.5)*1.0/100 - int(sum_k*100 + 0.5)*1.0/100
print 'k = %d, sum_k = %f, sum(eqn based) = %f, diff = %f, diff(rounded sum) = %f' % (k,sum_k,sum_k_eqn,sum_k_eqn-sum_k, diff_after_rounded)
Output:
~~~~~~
k = 1, sum_k = 1.000000, sum(eqn based) = 1.077200, diff = 0.077200, diff(rounded sum) = 0.080000
k = 2, sum_k = 1.500000, sum(eqn based) = 1.520347, diff = 0.020347, diff(rounded sum) = 0.020000
k = 3, sum_k = 1.833333, sum(eqn based) = 1.842479, diff = 0.009146, diff(rounded sum) = 0.010000
k = 4, sum_k = 2.083333, sum(eqn based) = 2.088494, diff = 0.005161, diff(rounded sum) = 0.010000
k = 5, sum_k = 2.283333, sum(eqn based) = 2.286638, diff = 0.003305, diff(rounded sum) = 0.010000
k = 30, sum_k = 3.994987, sum(eqn based) = 3.995064, diff = 0.000077, diff(rounded sum) = 0.010000
So what I did was handled these specific cases of k specially and for others used the equation.
Regards,
Kaushik Acharya
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator