fork(1) download
  1. def choose(n,k):
  2. if k == 0: return 1
  3. return choose(n-1,k-1) * n // k
  4.  
  5. from heapq import heappush, heappop
  6.  
  7. N = int( input() )
  8. probs = [ float(x) for x in input().split() ]
  9.  
  10. # generate all equivalence classes and push them into the priority queue
  11. Q = []
  12. for s in range(N+1):
  13. for c in range(N+1-s):
  14. for r in range(N+1-s-c):
  15. f = N-s-c-r
  16. pp = probs[0]**s * probs[1]**c * probs[2]**r * probs[3]**f
  17. cnt = choose(N,s) * choose(N-s,c) * choose(N-s-c,r)
  18. heappush( Q, (pp,cnt) )
  19.  
  20. # build Huffman code, always processing all equivalent nodes at once
  21. # note that the cost is computed incrementally:
  22. # each time we merge two vertices into one, we add the cost of those two edges
  23.  
  24. total_cost = 0
  25. while True:
  26. pp, cnt = heappop(Q)
  27. if cnt > 1:
  28. half = cnt//2
  29. total_cost += 2*pp*half
  30. heappush( Q, (2*pp,half) )
  31. if cnt%2: heappush( Q, (pp,1) )
  32. else:
  33. if len(Q)==0: break
  34. pp2, cnt2 = heappop(Q)
  35. total_cost += pp+pp2
  36. heappush( Q, (pp+pp2,1) )
  37. if cnt2 > 1: heappush( Q, (pp2,cnt2-1) )
  38.  
  39. print('{:.12f}'.format(total_cost))
Success #stdin #stdout 0.02s 8736KB
stdin
2
0.9 0.049999 0.05 0.000001
stdout
1.457509949996