No.560 ふしぎなナップサック

■■■問題■■■

グレート岡山大国に住む大岡くんは、魔法が使えます。

魔法が使える大岡くんは、
M個のビスケットが入っている時に叩くと
中のビスケットが M+1 個になるふしぎなポケットがあるという噂を聞いて、
自分も似たようなものを作ってみようと思いました。

ただ、ビスケットがどれだけ増えてもそこまで嬉しくないし、
1枚ずつしか増えないのも非効率的だな・・・と思った大岡くんは、
試行錯誤の結果、以下のようなお金が増えるナップサックを作ることに成功しました。

ナップサックの中にM円入っているときにナップサックを1回叩くと、

●3分の1の確率で中身が M×2 円になる
●3分の1の確率で中身が M+1 円になる
●3分の1の確率で中身が 0 円になる

(ただし、各回の試行の結果は前後の結果や中身の状態などに依らず独立とする)

しかし大岡くんは、実際にこのナップサックを使ってお金を増やせるのかとても不安になりました。
そこで、大岡くんのために最初にM円入っているナップサックを
ちょうどN回叩いたときのナップサックの中身の金額の期待値を求めてあげてください。

■■■入力■■■

M N

1行に、最初にナップサックに入っている金額Mとナップサックを叩く回数Nが空白区切りで与えられます。
入力は全て整数で、以下の制約を満たします。

●0 <= M,N <= 1000

■■■出力■■■

ナップサックをちょうどN回叩いたのちのナップサックの中身の金額を出力してください。
10の-8乗以下の誤差が許容されます。
最後に改行してください。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("100 2");
            //100.666666666667
            //100円入ったナップサックを2回叩くと、
            //等確率で400円,201円,0円,202円,102円,0円,0円,1円,0円のいずれかになります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 30");
            //10
            //大岡くんは優秀な魔法使いなので、
            //0円の状態からでもお金を生み出すことができます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("114 514");
            //285.333333333333
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int M = wkArr[0];
        int N = wkArr[1];

        decimal Answer = M;
        for (int I = 1; I <= N; I++) {
            Answer += 1M / 3M;
        }
        Console.WriteLine(Answer);
    }
}

解説

最初の金額をMとして、
試行1回後の金額の期待値は、

(2*M + M+1 ) / 3 = M + 1/3
となります。