Skip to content

Instantly share code, notes, and snippets.

@nishidy nishidy/c.hs
Created May 6, 2016

Embed
What would you like to do?
Google Code Jam 2016 Qualification Round : Problem C. Coin Jam (Only for small)
import Data.Char
import GHC.Float
import Debug.Trace
testloop :: Int -> Int -> IO ()
testloop i t | i>t = return ()
--testloop i t = getLine >>= \x-> trace(x) (lineloop x)
testloop i t = getLine >>= lineloop >>= \x-> putStrLn ("Case #"++(show i)++":\n"++x) >> testloop (i+1) t
lineloop :: String -> IO String
lineloop s = testmain n j
where
n = read $ (!!0) $ words s
j = read $ (!!1) $ words s
testmain :: Int -> Int -> IO String
--testmain n j = return $ foldl1 conc $ trace((show n)++","++(show j)) (answer n j)
testmain n j = return $ foldl1 (conc "\n") $ fmap concdiv $ answer n j
conc :: String -> String -> String -> String
conc m a b = a++m++b
concdiv :: String -> String
concdiv x = x++" "++(foldl1 (conc " ") $ fmap show $ fmap takenum $ takenums x)
takenum :: Int -> Int
takenum i =
case (divnum 2 i) of
Just n -> n
Nothing-> 0
answer :: Int -> Int -> [String]
answer n j = take j answers
where
coins = bitlist 1 (n-2)
--answers = trace(foldl1 (conc " ") $ take 3 coins) (filter jamcoin coins)
answers = filter jamcoin coins
jamcoin :: String -> Bool
--jamcoin x = trace(x) (all testnum $ takenums x)
jamcoin x = all testnum $ takenums x
subbits :: Int -> Int -> String
subbits n k | k==0 = if n >= 1 then "1" else "0"
subbits n k = x++y
where
x = if n >= (2^k) then "1" else "0"
y = if n >= (2^k) then subbits (n-(2^k)) (k-1) else subbits n (k-1)
bitlist :: Int -> Int -> [String]
bitlist k n = s:ss
where
s = "1"++(subbits k (n-1))++"1"
ss= bitlist (k+1) n
takenums :: String -> [Int]
takenums s = take 9 $ numlist s 2
type Base = Int
numlist :: String -> Base -> [Int]
numlist s b = x:xs
where
--x = trace(s) (calcnum 0 b $ reverse s)
x = calcnum 0 b $ reverse s
xs= numlist s (b+1)
calcnum :: Int -> Base -> String -> Int
calcnum k b [] = 0
--calcnum k b (x:xs) = trace(x:xs) (k+ks)
calcnum i b (x:xs) = k+ks
where
k = (digitToInt x) * (b^i)
ks= calcnum (i+1) b xs
testnum :: Int -> Bool
testnum i =
case (divnum 2 i) of
Just _ -> True
Nothing-> False
type Div = Int
divnum :: Div -> Int -> Maybe Int
divnum d n | (n `mod` d)==0 = Just d
divnum d n | d>=float2Int(sqrt(int2Float(n))) = Nothing
divnum d n = divnum (d+1) n
main = getLine >>= \t-> testloop 1 $ read t
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.