{-# LANGUAGE BangPatterns #-} import System.Environment import Data.Decimal import Data.Ratio import Data.Vector import qualified Data.Vector as V import qualified Data.Vector.Unboxed as U solve :: (Fractional a, Ord a) => Int -> Int -> a solve r b = go r b where tab = V.generate (r+1) (\r -> V.generate (b+1) (\b -> go r b)) look r b = tab V.! r V.! b go 0 b = 0 -- stop when there's only black cards go r 0 = fromIntegral r -- take all the remaining red cards go r b = max 0 (fromIntegral r/fromIntegral (r+b) * (look (r - 1) b + 1) + fromIntegral b/fromIntegral (r+b) * (look r (b - 1) - 1)) -- λ> solve 26 26 :: Rational -- 41984711742427 % 15997372030584 -- λ> 41984711742427 / 15997372030584 -- 2.624475548993925 solveLayers :: Int -> Int -> Double solveLayers fr fb = go 0 (U.fromList [0]) where go !n !tab | n == fr + fb = look fr | otherwise = go (n+1) $ U.generate (n+2) (\r -> let b = n + 1 - r p_r = fromIntegral r/fromIntegral (r+b) p_b = fromIntegral b/fromIntegral (r+b) in case (r,b) of (0,b) -> 0 (r,0) -> fromIntegral r (r,b) -> max 0 (p_r * (look (r - 1) + 1) + p_b * (look r - 1))) where look r = tab U.! r main = do [str_num] <- getArgs let n = read str_num :: Int print (solveLayers n n :: Double)