問題概要
3 つの整数 $A, B, C$ がある．これらに対し，「一つの整数を選び，値を $2$ 倍したものと置き換える」という操作を $K$ 回まで行える．
以下の 2 つの条件を満たすことはできるか？
- $A < B$
- $B < C$
制約
- $1 \leq A, B, C, K \leq 7$
解法
まず，$A$ は 3 整数の中で最も小さい値になって欲しいので，$A$ に対して操作をするのは明らかに無駄です．残りは $B, C$ ですが，$C$ をどうするかは $B$ が決まらないとよく分からないので，結局小さい方から条件を満たさせることにして，
- $A < B$ になるまで $B$ に操作
- $B < C$ になるまで $C$ に操作
- 操作回数が $K$ 回以内に収まっているか判定
という手順で問題を解くことになります．
計算量は，値が倍々で大きくなり，特定の値を超えたら終了するということから，$O( \log \max\{ A, B, C \} )$ 時間となります．
コード
main = do [ r, g, b ] <- readInts k <- readInt putStrLn $ which "Yes" "No" $ solve r g b <= k solve r g b | g <= r = 1 + solve r ( g * 2 ) b | b <= g = 1 + solve r g ( b * 2 ) | otherwise = 0
