codeforces - 110 - C (hs)

C.hs

{-# OPTIONS_GHC -O2 -XNoMonomorphismRestriction #-}
{-# LANGUAGE BangPatterns #-}
{-(c) gorlum0 [at] gmail.com-}
import Data.Array
import Control.Monad (forM_)
maxn = 10^6

dp :: Array Int Int
dp = array bnds [(i, f i) | i <- range bnds]
    where
    bnds = (-6, maxn)
    f 0 = 1
    f i
        | i < 0         = 0
        | dp!(i-7) /= 0 = 7
        | dp!(i-4) /= 0 = 4
        | otherwise     = 0

lucky n
    | dp!n == 0 = [-1]
    | otherwise = f n
    where
    f 0 = []
    f n = dp!n : f (n - dp!n)

main = do
    ls <- lines `fmap` getContents
    let ns = map read ls
    forM_ [lucky n | n <- ns] $
        putStrLn . concat . map show . reverse