Rachael's clons P79374
Dr. Eldon Tyrell is studying the endurance of Nexus-6 replicants. He has constructed many identical Rachaels, so he can do this experiment as many times as he likes: He enters with a Rachael into an elevator, goes up to a height of x meters (this costs c x dollars in energy for some constant c), and pushes Rachael so that it falls down. If Rachael breaks, Dr. Tyrell loses its value (v dollars). Otherwise, Dr. Tyrell loses nothing (but implants a new memory to Rachael so that it does not take revenge!).
Dr. Tyrell already knows that Rachaels break when they fall from a height of H meters (an integer number), but now he wants to discover the minimum height h at which they break, assuming that h is also integer. Dr. Tyrell wants to save as much money as possible. (Ingenuously, because the renegade Nexus-6 Roy Batty is going to crush its creator’s head very soon…)
Help Dr. Tyrell in this two settings: (1) in the worst case; (2) in the average case, supposing that any height 1, 2, …, H has the same probability of being h.
For instance, let H = 4, c = 2 and v = 5. Here, the optimal strategy to minimize the worst-case cost of discovering h starts dropping a Rachael from height 2. If the replicant does not break, we drop it again from height 3; otherwise, we drop another Rachael from height 1. The worst cost happens when both replicants break, for a total cost of 2 · 2 + 5 + 2 · 1 + 5 = 16.
With the same values, the optimal strategy to minimize the average-case cost starts dropping a Rachael from height 1. With probability 1/4 it will break, in which case we discover that h = 1. If it does not break, we drop it again from height 2, and again from height 3 if necessary. Therefore, the average cost of this strategy is
| 2 · 1 + |
| · 5 + |
| ⎛ ⎜ ⎜ ⎝ | 2 · 2 + |
| · 5 + |
| ⎛ ⎜ ⎝ | 2 · 3 + |
| · 5 | ⎞ ⎟ ⎠ | ⎞ ⎟ ⎟ ⎠ | = 11.75 . |
Input
Input consists of several cases, each one with three integer numbers H, c and v. Assume 1 ≤ H ≤ 100, 0 ≤ c ≤ 100 and 0 ≤ v ≤ 100.
Output
For every case, print the minimum cost to discover h, in the worst case (an integer number), and also in the average case (a real number with four digits after the decimal point). The input cases have no precision issues.
Input
4 2 5 1 2 5 5 0 3 8 1 0 32 52 85 99 1 2 100 11 97
Output
16 11.7500 0 0.0000 3 2.4000 15 12.0000 5961 4341.6562 471 332.6364 5481 3931.1700
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++