問題一覧 > 通常問題

No.425 ジャンケンの必勝法

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 101
作問者 : はむこはむこ / テスター : btkbtk
7 ProblemId : 1307 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-09-22 19:11:55

問題文

ジャンケンには必勝法がある。
人間には「あいこのあとには、そのあいこの手と同じ手を出しにくい」という心理的バイアスがある。
これを利用すると、「あいこのあとに、そのあいこの手に負ける手を出す」ことで勝率が上がることがわかる。

カモ君とネギ君が、ジャンケンで勝負する。
カモ君の心理的バイアスは非常に強いので、あいこのあとには必ず違う手の中から確率1/2でランダムに出す。
ネギ君は、ジャンケンの必勝法を知っている。

例えば、「パー」であいこになった場合、カモ君は次にグーかチョキしか出さない。
ネギ君は、あいこの手「パー」に負けるグーを出せば、絶対に負けることはない。

しかし、毎回必勝法を使うとバレる危険があるので、ネギ君は確率$p$でしか必勝法を使わない。
必勝法を使わない時は、全ての手の中から確率1/3でランダムに出す。

さらにネギ君は非常に慎重なので、あいこのたびに確率$p$を以下のルールを用いて変える。
(1) 初めてのあいこでは、確率$p$を$p_0$とする。
(2) 二回目以降のあいこで、前回に必勝法を使っていたら、確率$p$を$p_{prev}-q$とする($p_{prev}$は前回の確率$p$)。$p$が$0$を下回ったら、$p$は$0$にする。
(3) 二回目以降のあいこで、前回に必勝法を使っていなかったら、確率$p$を$p_{prev}+q$とする($p_{prev}$は前回の確率$p$)。$p$が$1$を超えたら、$p$は$1$にする。

最初の手は前の結果がないため、必勝法も心理的バイアスもないことに注意せよ。
つまり、両者とも全ての手の中から確率1/3でランダムで出す。

今、カモ君とネギ君が1回勝負がつくまでジャンケンをする。ネギ君が勝つ確率を求めよ。

入力

$p_0\ q$

$0 \leq p_0 \leq 100$, 整数, 百分率表記(%表記)
$0 \leq q \leq 100$, 整数, 百分率表記(%表記)

出力

ネギ君が勝つ確率を求めてください。
誤差は$10^{-6}$まで許容されます。
最後に改行してください。

サンプル

サンプル1
入力
0 0
出力例
0.5

カモ君に心理的バイアスがあっても、ネギ君が常にランダムに出すならば、勝率は50%です。

サンプル2
入力
100 0
出力例
0.666666666666

バレる危険を恐れずに常に必勝法を使うと、2/3まで勝率が上がります。

サンプル3
入力
100 100
出力例
0.6

必勝法を使う・使わないを交互に繰り返すと60%で勝てます。

ジャンケンの進行は以下のようになります。
1回目の勝負では、二人とも確率1/3で全ての手を出すので、ネギ君は1/3の確率で勝ちます。あいこなら次の勝負へ。
2回目の勝負では、初めてのあいこなのでルール(1)より、ネギ君は$p=p_0=1$の確率で必勝法を使います。したがってネギ君は1/2の確率で勝ちます。あいこなら次の勝負へ。
3回目の勝負では、前回必勝法を使ってあいこになったのでルール(2)より、ネギ君は$p=p_{prev}-q=0$の確率で必勝法を使います。したがってネギ君は1/3の確率で勝ちます。あいこなら次の勝負へ。
4回目の勝負では、前回必勝法を使わずあいこになったのでルール(3)より、ネギ君は$p=p_{prev}+q=1$の確率で必勝法を使います。したがってネギ君は1/2の確率で勝ちます。あいこなら次の勝負へ。
5回目の勝負では、前回必勝法を使ってあいこになったのでルール(2)より、ネギ君は$p=p_{prev}-q=0$の確率で必勝法を使います。したがってネギ君は1/3の確率で勝ちます。あいこなら次の勝負へ。
以下繰り返しです。

サンプル4
入力
20 80
出力例
0.548148148148148

サンプル5
入力
3 14
出力例
0.51149191514

出力には$10^{-6}$まで誤差が許容されます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。