Rachael's clons P79374


Statement
 

pdf   zip

html

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 + 
1
4
 · 5 + 
3
4



2 · 2 + 
1
3
 · 5 + 
2
3
 

2 · 3 + 
1
2
 · 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.

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28