haskell - CodeChef 超时

Question

我是CodeChef的新手，想尝试几个问题，所以我解决了“Bytelandian金币”问题。 ( http://www.codechef.com/problems/COINS/ ) 我在计算机上得到即时结果，CodeChef 设置了 9 秒的时间限制，但我仍然收到来自 CodeChef 的超时。我不知道是什么原因造成的了。任何提示都会有帮助。

我的代码:

module Main where

import qualified Data.Map as M
import Data.Map (Map)
import Data.Maybe

main = do
    catch (main' M.empty 1) (const $ return ()) 

main' _ 11 = return ()
main' m c = do
    x <- readLn
    let (k,m2) = sol m x
    print k
    main' m2 (c+1)


sol :: Map Integer Integer -> Integer -> (Integer, Map Integer Integer)
sol m x     |M.member x m = (fromJust $ M.lookup x m,m)
            |x > x2+x3+x4 = (x,M.insert x x m)
            |otherwise = (fullSoll, M.insert x fullSoll m4)
    where
        x2 = div x 2
        x3 = div x 3
        x4 = div x 4
        (sx2, m2) = sol m x2
        (sx3, m3) = sol m2 x3
        (sx4, m4) = sol m3 x4
        fullSoll = sx2+sx3+sx4

Answer 1

当x == 0时，您的sol不会终止。当x为1时就可以了，因为x2、x3、x4都是0，并且它们的总和小于x，即第二个守卫是真的，并且没有递归。但是，当输入为 0 时，就会开始递归情况，并且永远不会终止。