Score : 300 points
Takahashi is now competing in a programming contest, but he received TLE in a problem where the answer is YES
or NO
.
When he checked the detailed status of the submission, there were N test cases in the problem, and the code received TLE in M of those cases.
Then, he rewrote the code to correctly solve each of those M cases with 1/2 probability in 1900 milliseconds, and correctly solve each of the other N-M cases without fail in 100 milliseconds.
Now, he goes through the following process:
Let the expected value of the total execution time of the code be X milliseconds. Print X (as an integer).
Input is given from Standard Input in the following format:
N M
Print X, the expected value of the total execution time of the code, as an integer. It can be proved that, under the constraints in this problem, X is an integer not exceeding 10^9.
1 1
3800
In this input, there is only one case. Takahashi will repeatedly submit the code that correctly solves this case with 1/2 probability in 1900 milliseconds.
The code will succeed in one attempt with 1/2 probability, in two attempts with 1/4 probability, and in three attempts with 1/8 probability, and so on.
Thus, the answer is 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800.
10 2
18400
The code will take 1900 milliseconds in each of the 2 cases, and 100 milliseconds in each of the 10-2=8 cases. The probability of the code correctly solving all the cases is 1/2 \times 1/2 = 1/4.
100 5
608000