| ENG RUS | Timus Online Judge |
Discussion of Problem 1776. Anniversary FireworkArtem Khizha [DNU] WA# 6 [11] // Problem 1776. Anniversary Firework 9 Oct 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 vgu Re: WA# 6 [6] // Problem 1776. Anniversary Firework 9 Oct 2010 20:42 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]. r1d1 Re: WA# 6 [1] // Problem 1776. Anniversary Firework 10 Oct 2010 01:02 How ans for N=400? Artem Khizha [DNU] Re: WA# 6 // Problem 1776. Anniversary Firework 10 Oct 2010 02:00 N = 400 ANS = 184.652746446 Edited by author 10.10.2010 02:19 Artem Khizha [DNU] Re: WA# 6 // Problem 1776. Anniversary Firework 10 Oct 2010 02:04 Thank you, vgu, your tests helped a lot. Proba Re: WA# 6 [2] // Problem 1776. Anniversary Firework 11 Oct 2010 12:19 How ans for N=6? bsu.mmf.team Re: WA# 6 [1] // Problem 1776. Anniversary Firework 11 Oct 2010 18:47 33.333333333 Vasily Slesarev Re: WA# 6 // Problem 1776. Anniversary Firework 21 May 2011 16:02 Please give tests for N= 20 30 40 50 60 70 80 90 100 olpetOdessaONU [1 2/3] Re: WA# 6 [3] // Problem 1776. Anniversary Firework 10 Oct 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. bsu.mmf.team Re: WA# 6 [2] // Problem 1776. Anniversary Firework 10 Oct 2010 16:47 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. Ibragim Atadjanov (Tashkent U of IT) Re: WA# 6 // Problem 1776. Anniversary Firework 27 Oct 2010 16:20 Which of these formulas correct for this problem 1. M(A) + M(B) - M(AB) 2. M(A)*M(B/A) Amirbekov Artem[Ivanovo SPU] Re: WA# 6 // Problem 1776. Anniversary Firework 9 Nov 2011 03:17 Could you explain what formula is for max(M(A),M(B))? bsu.mmf.team wrote 10 October 2010 16:47 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. |