C - HSI Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。

提出の詳細を見ると，テストケースは全てで N ケースあり，そのうち M ケースでTLEしていました。

そこで高橋くんは, M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し， 残りの N-M ケースではそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。

そして，以下の操作を行います。

  • このプログラムを提出する。
  • 全てのケースの実行が終わるまで待機する。
  • もし M ケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。
  • これを，一度で全てのケースに正解するまで繰り返す。

この操作が終了するまでの，プログラムの実行時間の総和の期待値を X msとした時，X を出力してください。

なお，X は整数で出力してください。

制約

  • 入力は全て整数
  • 1 \leq N \leq 100
  • 1 \leq M \leq {\rm min}(N, 5)

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

実行時間の総和の期待値 X を整数で出力してください。 なお，X はこの問題の制約下で，10^9 以下の整数となることが証明できます。

入力例 1

1 1

出力例 1

3800

この入力だとケースは 1 ケースだけであり，1900 ms かかって 1/2 の確率で正解するプログラムを投げ続けます。

つまり 1 回で正解する確率は 1/2, 2 回で正解する確率は 1/4, 3 回で正解する確率は 1/8 です。

よって答えは 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800 です。

入力例 2

10 2

出力例 2

18400

2 ケースで 1900 ms かかり，10-2=8 ケースで 100 ms かかるプログラムを投げ続けます。 全てのケースで正解する確率は 1/2 \times 1/2 = 1/4 です。

入力例 3

100 5

出力例 3

608000

Score : 300 points

Problem Statement

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:

  • Submit the code.
  • Wait until the code finishes execution on all the cases.
  • If the code fails to correctly solve some of the M cases, submit it again.
  • Repeat until the code correctly solve all the cases in one submission.

Let the expected value of the total execution time of the code be X milliseconds. Print X (as an integer).

Constraints

  • All input values are integers.
  • 1 \leq N \leq 100
  • 1 \leq M \leq {\rm min}(N, 5)

Input

Input is given from Standard Input in the following format:

N M

Output

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.

Sample Input 1

1 1

Sample Output 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.

Sample Input 2

10 2

Sample Output 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.

Sample Input 3

100 5

Sample Output 3

608000