2008 Round 1A
The problem is equivalent to finding a assignment to variables to satisfy an expression in conjunctive normal form, such as:
(a | b | c) & (a | ~d | e) & ...
Truth corresponds to unmalted; variables assigned false values correspond to malted milkshakes.
Fortunately there’s one additional proviso that makes this problem trivial: each clause has at most one negated variable. This means we can:
Look for a singleton clause. If none exist, then we can assign the remaining variables to true, and output a solution.
Otherwise, the variable in the singleton clause must be assigned a certain value to satisfy the expression. We add the assignment to an accumulator list, remove all clauses that contain the same literal, and remove any occurrences of the negated literal from the remaining clauses.
If any of the clauses are now empty, then there is no solution. Otherwise go back to step 1.
import Data.List import Data.List.Split import Data.Maybe import qualified Data.Map as M import Jam main = jam $ do [[n], [m]] <- getintsn 2 let showSol sol = unwords $ show . flip (M.findWithDefault 0) sol <$> [1..n] f sol cs |  `elem` cs = "IMPOSSIBLE" | otherwise = maybe (showSol sol) g $ find ((1 ==) . length) cs where g [[x, y]] = f (M.insert x y sol) $ delete [x, 1 - y] <$> filter (notElem [x, y]) cs f M.empty . map (chunksOf 2 . tail) <$> getintsn m
I spent a long time on the wrong path because my first instinct was to attempt to solve the question for any number of the form a + b sqrt(5).
Eventually I realized there was something special about the choice of 3 and sqrt(5). I was lucky sqrt(5) was chosen, because it triggered a memory of Binet’s formula. Recall the second term is always less than 1, so we can evaluate the formula by finding the integer closest to the first term.
This led me to consider:
f n = (3 + sqrt 5)^n + (3 - sqrt 5)^n.
This is always an integer because all the terms involving sqrt(5) cancel out. Furthermore, 3 - sqrt(5) < 1, so the answer is simply:
(f n - 1) `mod` 1000
Since 3 + sqrt(5) and 3 - sqrt(5) are the roots of x2 - 6x + 4, we can describe f(n) with the recurrence f(n) = 6 f(n-1) - 4 f(n-2) and f(0) = 2, f(1) = 6.
import Control.Monad import Data.List import Text.Printf import Jam m = [[6, -4], [1, 0]] mul [[a, b], [c, d]] [[x, y], [z, w]] = map (map (`mod` 1000)) [[a*x + b*z, a*y + b*w], [c*x + d*z, c*y + d*w]] pow m 0 = [[1, 0], [0, 1]] pow m 1 = m pow m a | mod a 2 == 1 = mul m2 m | otherwise = m2 where m2 = join mul $ pow m $ div a 2 main = jam $ do [n] <- getints return $ printf "%03d" (let [[a, b], _] = pow m (n - 1) in (a*6 + b*2 - 1) `mod` 1000 :: Integer)
We use a little trick. If f has type a -> a -> a, then thanks to the Reader monad:
join f x = f x x