import Data.Array.IO import Data.Char import System.IO import Control.Monad import Control.Applicative one :: [a] -> [(a, [a])] one xs = sub xs [] where sub [] _ = [] sub (x:xs) ac = (x, xs++ac) : (sub xs (x:ac)) two :: [a] -> [(a, a, [a])] two [] = [] two [a] = [] two xs = do (x, rest) <- one xs do (y, rest) <- one rest return (x, y, rest) data Expr = Val Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr type Number = (Expr, Int) eval :: Number -> Int eval = snd apply :: [Number] -> [[Number]] apply xs = concat $ do ((e, x), (f, y), rest) <- two xs return [ (Add e f, x + y) : rest, (Sub e f, x - y) : rest, (Mul e f, x * y) : rest ] bfs :: Int -> [[Number]] -> [Number] bfs n [] = [] bfs n ([x] : rest) = (if (eval x) == n then [x] else []) ++ (bfs n rest) bfs n (xs : rest) = bfs n (rest ++ (apply xs)) instance Show Expr where show (Val n) = show n show (Add e f) = "(" ++ show e ++ " + " ++ show f ++ ")" show (Sub e f) = "(" ++ show e ++ " - " ++ show f ++ ")" show (Mul e f) = "(" ++ show e ++ " * " ++ show f ++ ")" toVal :: Int -> Number toVal n = (Val n, n) solve a b c d = do let anss = bfs 10 [[toVal a, toVal b, toVal c, toVal d]] if null anss then print 0 else print $ fst $ head $ anss main = do [a,b,c,d] <- (map read . words)<$>getLine :: IO [Int] if (minimum [a,b,c,d]) == 0 then return () else solve a b c d >> main