Project Euler 527 - Randomized Binary Search

Source

Project Euler 527

問題概要

正整数 $N$ が与えられた時,次のようなゲームを考える.
B君は $1$ から $N$ までの整数の中から $1$ つの整数 $t$ を $1$ 回だけ一様にランダムに選ぶ.
A君はB君にある整数 $k$ を投げかけて,その整数が $t$ より大きいか,$t$ より小さいか,$t$ と等しいか何回でも聞くことができる.
投げかけた整数が $t$ と等しくなるまでゲームを続ける.
この時,A君の戦略として,次の $2$ つのもの考える.
$1$ つ目の戦略では,A君は $t$ が $L$ 以上 $R$ 以下の整数であると知っている場合には,$\lfloor (L+R)/2 \rfloor$ を投げかける.
$2$ つ目の戦略では,A君は $t$ が $L$ 以上 $R$ 以下の整数であると知っている場合には,$L$ 以上 $R$ 以下の整数の中から一様にランダムに整数を選びそれを投げかける.
$1$ つ目の戦略において,投げかける整数の回数の期待値を $B(N)$ とし, $2$ つ目の戦略において,投げかける整数の回数の期待値を $R(N)$ とする.
$R(10^{10}) - B(10^{10})$ を小数点以下 $8$ 桁で求める問題.

解法

この部分を表示するには以下のフォームにパスワードを入力する必要があります.
パスワードはこの問題の答え

パスワード:


Current time: 2017年07月24日15時46分15秒
Last modified: 2015年09月27日17時19分41秒 (by laycrs)
Tags: Competitive_Programming Project_Euler
トップページに戻る

Logged in as: unknown user (not login)

ログイン: