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