Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:Who solved it in mathematical way?

Posted by kaushik_acharya at 2013-06-17 22:48:57 on Problem 1003
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator