This is my first cooperation with my new teammates, WDP and WHD. Our team is called ACME, which can be understood as AC me, or it original meaning the peak.

#A AC 8min 1 wrong try by WHD

#I AC 17min

It is a typical DP problem.

#B AC 76min 1 wrong try

It is a math problem. WDP told me the meaning of the problem, and I come up with a formula soon.

Let f(p) be p*sum{p^n*(1-p)^i*C(i,n+1)*(n-i);i=0 to n}.

The answer will f(p)+f(1-p).

However for some certain i, p^n*(1-p)^i*C(i,n+1)*(n-i) can be too small, to avoid underflow errors we can calculate ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) instead.

When we use it, we use e^ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) and if ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) is too small we just ignore it.

We come up with a n^1.5*logn algorithm for problem C and got TLE. We also used the algorithm proved to be right to solve problem K, but didn’t get AC. I think it must be some bugs when facing edge cases.