Golden ratio （黄金比）

競プロ典型 90 問 53 日目 - Discrete Dowsing（★7)

import Control.Monad
import System.IO

main = readLn >>= flip replicateM_ sub

qry :: Int -> IO Int
qry = (>> readLn) . put . ("? " ++) . show

ans = put . ("! " ++) . show

put = (>> hFlush stdout) . putStrLn

sub = do
  n <- readLn
  case n of
    1 -> qry 1 >>= ans
    2 -> max <$> qry 1 <*> qry 2 >>= ans
    _ -> do
      let m = mid 1 n
      a1 <- qry 1
      am <- qry m
      an <- qry n
      sol (1,a1) (m,am) (n,an) >>= ans

sol (l,al) (m,am) (r,ar)
  | r-l<3   = return $ maximum [al,am,ar]
  | m-l>r-m = do
      let m' = mid l m
      am' <- qry m'
      if      am'>am then sol (l,al) (m',am') (m,am)
      else if am'<am then sol (m',am') (m,am) (r,ar)
      else do
        let m'' = mid m' m
        am'' <- qry m''
        sol (m',am') (m'',am'') (m,am)
  | otherwise = do
      let m' = mid m r
      am' <- qry m'
      if      am>am' then sol (l,al) (m,am) (m',am')
      else if am<am' then sol (m,am) (m',am') (r,ar)
      else do
        let m'' = mid m m'
        am'' <- qry m''
        sol (m,am) (m'',am'') (m',am')

ϕ = (sqrt 5-1)/2

mid :: Int -> Int -> Int
mid i j = round ((1-ϕ)*fromIntegral i+ϕ*fromIntegral j)