Given an unknown target fee uniform on [L,R], maximize expected gold by naming fees over time, where each attempt or save-reload costs 100 ms and time is capped by T.
Hard8Dynamic programmingMathProbabilityGame theoryNo attempts yetTime limit2sMemory limit512 MBYou are playing a video game called the Association for Control of Monsters, or ACM. In the game you work for the ACM as a witcher named Jerry, and your job is to kill monsters with your silver sword. You do not work for free. When a non-playing character (an NPC) has a contract for you, you haggle over the fee.
Haggling works like this. Before the haggling starts, the NPC picks an integer number of gold pieces t at random from L to R, inclusive, every value equally likely. You name a fee, and the NPC accepts it if it is at most t, otherwise the NPC rejects it and you may name another one. Every fee you name must be an integer from L to R, inclusive. Watching the NPC accept or reject takes 100 milliseconds. Your attention span is short, so you get bored once T milliseconds have passed.
You saved the game just as the haggling started. If the NPC accepts your fee, you may take the gold and finish, or you may load that save and haggle again knowing everything you have learned so far. Loading the save costs 100 milliseconds on top of the 100 milliseconds of NPC dialogue. The value of t does not change when you load the save. If the NPC rejects your fee you may name another one, and if that one is rejected you may name another, repeating while time remains. The moment you have used more than T milliseconds you get bored and stop at once, even in the middle of watching dialogue or loading a save, and you collect no gold on that run.
Find the highest expected amount of gold you can collect.
The expected value is the average amount of gold over an infinite number of rounds of haggling. Suppose L=2, R=4, T=250, and your plan is to name 4 first and then name 2 if the 4 is rejected. Over an infinite number of runs, t is 2, 3 and 4 equally often. The plan collects 2 when t is 2 or 3, and collects 4 when t is 4, so its expected value is (2+2+4)/3=8/3.
One line with three integers L, R and T (1≤L≤80, L≤R≤80, 1≤T≤10000).
Print one line with the highest expected amount of gold you can collect, rounded to exactly 9 digits after the decimal point.