4

これは、昨日インタビューストリートで終了したプログラミングコンテストでの質問でした。

アリスとボブはゲームをします。ラウンドi（i> = 1）での操作は次のとおりです。

  • アリスはボブに2*i-1ドルを支払います、
  • アリスは偏ったコインを投げます、
  • コインの結果がk連続ラウンドのヘッドだった場合、ゲームは停止します。それ以外の場合、ゲームは続行されます。

kと、トスの結果がヘッド（p）である確率を考えると、プログラムは、アリスがボブに支払う予想金額と、予想されるラウンド数を見つける必要があります。

入力

入力の最初の行には、テストケースの数が含まれています（T <= 50）。次の各T行には、単一のスペースで区切られたpとkが含まれています。pは、0.6 <= p<=1となる小数点以下2桁までの10進数です。kは0<k<=20となる正の整数です。

出力

テストケースごとに、2つの整数を出力します。最初の数字は予想されるゲームのラウンド数の整数部分であり、2番目の数字は予想されるドル数の整数部分であり、アリスはボブに支払います。

サンプル入力

3

0.6 1

1 20

0.80 8

サンプル出力

1 3

20 400

24 976

私は問題の最初の部分、つまりゲームの予想ラウンド数を取得しました。私は次のコードでそれを手に入れました

if __name__ == '__main__':
    t = int(raw_input())   
    while t :
        t -= 1
        temp = str(raw_input())
        p,k = temp.split(' ')
        p = float(p)
        k = int(k)

        #print p,k
        ans  = 0.0
        num = k * (p**k)
        den = 1
        q = 1.0 - p
        for N in range(1,k+1):
            den = den - ((p**(N-1))*q)
            num = num + (N*(p**(N-1))*q)
            #print (N*(q**N))

        print int(num/den)

しかし、問題の2番目の部分はまだ私を困惑させています。つまり、アリスがボブに支払う予想金額です。期待されるペイオフはどのように計算できますか？

4

1 に答える 1

3

予想されるラウンド数がわかっている場合でも、発生する可能性のあるすべての支払いを平均する必要があります。これは、予想される停止時間に支払いを計算するよりも複雑であることを意味します。ここに核心の詳細があります：

期待値の技術的定義では、Xが確率変数の場合、Xの期待値は、X（w）* Pr（w）のすべての可能な結果wの合計であると述べていることを思い出してください。Xが正の整数の値を取る場合、Xの期待値はi=1からi*Pr（X = i）の無限大までの合計であるため、これを言い換えることができます。あなたの場合、私たちが扱っている確率変数は、T =ゲームが停止する時間、およびP=支払いです。

期待されるラウンド数はTの期待値であり、これはi=1からi*Pr（T = i）の無限大までの合計です。期待値の整数部分のみを要求するため、i * Pr（T = i）が1/2 ^ i未満になると、合計を停止できます。（i * Pr（T = i）<1/2 ^ iの場合に合計を停止するという考え方は、1/2 ^ iの合計が1になるというものですが、過小評価を避けるためにこれを微調整する必要がある場合があります。）

Pの期待値は少し複雑です。ゲームがjラウンド続く場合、ペイアウトはi = 1から2i-1のjまでの合計になり、j^2になります。したがって、j ^ 2の形式の支払いのみが発生し、Pr（P = j ^ 2）= Pr（T = j）になります。したがって、Pの期待値は、i=1からi^2 * Pr（P = i ^ 2）の無限大までの合計であり、i=1からi^2 * Pr（T =私）。ここでも、i ^ 2 * Pr（T = i）が1/2 ^ i未満になると、合計を停止できます。

于 2012-10-09T15:54:21.200 に答える