|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияWA# 6 Artem Khyzha 9 окт 2010 20:35 I'm again and again experiencing WA#6. Can you help me?
If you got AC, please, share the correct answers to some tests.
N = 7
N = 8
N = 9
N = 10
N = 19
N = 20
N = 399
N = 400 Your idea is not correct. I have WA#6 too.
N=7; ans = 38.0;
N=8; ans = 42.6666;
N=9; ans = 46.69841269841;
N=10; ans = 50.1746031746;
Try think about 2-parameters DP p[n][k]. N = 400
ANS = 184.652746446
Edited by author 10.10.2010 02:19 Thank you, vgu, your tests helped a lot. Please give tests for N=
20
30
40
50
60
70
80
90
100 Re: WA# 6 olpetOdessaONU [1 2/3] 10 окт 2010 14:48 WA6 got all the contestants, used dynamic formula
f(N) = 1/N * sum(i=0..n-1)max(f(i),f(N-i-1)) + 10
It's incorrect. This formula is almost correct. The following example will illustrate it. Imagine you have two groups of rockets (A and B) and you know, that group A will launch in 10 seconds with probability 1/2, and in 20 seconds with probability 1/2 (math expectation equals 15 in this case). The group B has probabilities 1/3 and 2/3 correspondingly (math expectation = 50/3). But a probability that all rockets will launch in 10 seconds equals 1/2 * 1/3 = 1/6 (it is almost evident), and in 20 seconds: 1 - 1/6 = 5/6. Math expectation = 55/3.
So, the only mistake in this formula is M(max(A,B)) != max(M(A),M(B)). Change this, and this fomula will be correct. By the way, I got AC using it. Which of these formulas correct for this problem
1. M(A) + M(B) - M(AB)
2. M(A)*M(B/A) Re: WA# 6 Amirbekov Artem[Ivanovo SPU] 9 ноя 2011 03:17 Could you explain what formula is for max(M(A),M(B))? This formula is almost correct. The following example will illustrate it. Imagine you have two groups of rockets (A and B) and you know, that group A will launch in 10 seconds with probability 1/2, and in 20 seconds with probability 1/2 (math expectation equals 15 in this case). The group B has probabilities 1/3 and 2/3 correspondingly (math expectation = 50/3). But a probability that all rockets will launch in 10 seconds equals 1/2 * 1/3 = 1/6 (it is almost evident), and in 20 seconds: 1 - 1/6 = 5/6. Math expectation = 55/3.
So, the only mistake in this formula is M(max(A,B)) != max(M(A),M(B)). Change this, and this fomula will be correct. By the way, I got AC using it. |
|
|
