AOJ 2301 - Sleeping Time

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2301

概要

範囲 [R, L) について，T を目指して K 回の二分探索する． しかし，確率 P で誤った方を選択してしまう．

このとき，最終的に辿りつく値 T' が T-E <= T' <= T+E となる確率を求める．

制約

• 0 <= K <= 30
• 0 <= R <= L <= 12
• 0 <= P <= 1
• 0 <= E <= 12
• 0 <= T <= 12

解法

シミュレーション． 一見 2^K になりそうに見えるが，

• [R, L) が T ± E の範囲から完全に外れたら 0
• [R, L) が T ± E の範囲に完全に含まれたら 1

という枝刈りがかなりできるので大丈夫．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 double P, E, T;
 7 
 8 double solve(int K, double L, double R)
 9 {
10   const double H = (L + R)/2.0;
11   if (K == 0) {
12     if (fabs(T - H) < E) {
13       return 1.0;
14     } else {
15       return 0.0;
16     }
17   }
18 
19   if (R < T-E || T+E < L) {
20     return 0.0;
21   } else if (T-E <= L && R <= T+E) {
22     return 1.0;
23   }
24 
25   if (H <= T) {
26     return P*solve(K-1, L, H) + (1.0-P)*solve(K-1, H, R);
27   } else {
28     return P*solve(K-1, H, R) + (1.0-P)*solve(K-1, L, H);
29   }
30 }
31 
32 int main()
33 {
34   int K;
35   double L, R;
36   cin >> K >> L >> R;
37   cin >> P >> E >> T;
38 
39   printf("%.6f\n", solve(K, L, R));
40   return 0;
41 }