|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||3||2||2||66.667%|
You are playing a video game called “The Association for Control of Monsters” (ACM). In this game, you work for the ACM as a witcher, and your name is Jerry. As a witcher, it is your job to kill hideous, and fictional, monsters with your silver sword. But you do not do this for free, instead you demand a fee for your work. When a non-playing character in the game (an NPC) has a contract for you, you will attempt to haggle with them.
Haggling is carried out as follows. The NPC will choose an integer amount of gold pieces, t, between L and R, inclusive. The NPC chooses t uniformly at random before the haggling starts. You will offer them a fee and they will accept the offer you make if it is at most t, otherwise they will reject the offer, after which you may make another offer. Each offer must be an integer value between L and R, inclusive. Watching the dialogue with the NPC when your offer is rejected or accepted takes 100 milliseconds. Since you are a hardcore gamer having a very short attention span, you get bored after T milliseconds.
You have saved the game state just as the haggling started, which means that if your offer is accepted by the NPC, you may reload this save and start again with the knowledge you gained (note that the value of t does not change when you reload the game). However, reloading the save also takes 100 milliseconds on top of the 100 milliseconds for the NPC’s dialogue. Note that if your offer is rejected, you can make another offer, and if that second offer is rejected, you can make another, and so on until you run out of time. If your offer is accepted, however, you may choose to either take the gold or reload the save. If you ever get bored (that is, use more than T milliseconds), then you must stop what you are doing (you might be half way through watching accept or reject dialogue, or loading a save) and you get no gold. To be the very best hardcore gamer, you must be able to haggle well, so you have decided to write a program to help. Given L, R and T, what is the highest expected value of gold you can get?
The expected value is the average amount of gold over an infinite number of different rounds of haggling. For example, say that L = 2, R = 4, T = 250 and our strategy is to make an offer of 4, then if it is rejected, make an offer of 2. This has an expected value of 8 3 gold. This is because the threshold value t picked by the NPC is equally likely to be 2, 3 or 4 over an infinite number of runs. This strategy earns 2 when t = 2, 3 and earns 4 when t = 4, so it has expected value (2+2+4)/3 = 8/3.
The input consists of a single line containing three integers L (1 ≤ L ≤ 80), R (L ≤ R ≤ 80) and T (1 ≤ T ≤ 10 000) as described above.
Display the highest expected value you can attain. Your answer should have an absolute or relative error of less than 10−6.
2 4 250
1 5 100