if k < m return 0 else

amount of 'good' results is equal to С(m), wher C() - Catalanas number
amount of 'bad' results is equal to sum(i = 0.. m, C(i))


for example for m = 3

( - big brother acts
) - smal brothers acts

good results are (independent of k)
((()))
(()())
(())()
()(())
()()()

bad results are
(()) )
()() )
() )
)

now we should calculate C(m) / sum(i = 0.. m, C(i))
C(m) / sum(i = 0.. m, C(i)) = 1 / (sum(i = 0.. m, C(i)) / C(m)) =
= 1 / sum(i = 0.. m, C(i) / C(m)) =
= 1 / sum( i = 0.. m, exp(ln(C(i)) - ln(C(m))) )
We can calculate ln(C(i)) using formula C(i) = F(2 * i) / F(i) / (i + 1), where F(N) = N!

ln(C(i)) = ln(F(2 * i)) - ln(F(i)) - ln(i + 1)
ln(F(i)) = sum(j = 1.. i, ln(j))

now we can calculate sum( i = 0.. m, exp(ln(C(i)) - ln(C(m))) ) accurate to some EPS, and can calculate answer for the task with some EPS.

I tryed to pass this algo, and it doesn't take AC.

Does it wrang algorithm? or it is not enought accurate?

Edited by author 12.03.2009 17:59