import Jam import Control.Applicative import Data.Char import Data.List.Split main = jam $ gets >> gets >>= \s -> return $ chr . foldl (\n c -> 2*n + fromEnum (c == 'I')) 0 <$> chunksOf 8 s
Code Jam to I/O 2015 for Women
We fold over a string to read a number in binary. We use fromEnum to convert a Bool to an Int; an alternative is to import Data.Bool and write bool 0 1 (c == 'I').
A fun exercise in combinatorics. In a given triple, label the component values a, b, c such that a <= b <= c.
First, we count the cases when all components are equal. There are k + 1 of these: one for each possible component value.
Otherwise, c - a == n for some n <- [1..v]. There are k - n + 1 possible solutions for this equation, one for each a <- [0..k - n].
Now, if a == b, then there are 3 possible orderings for these components: (a, a, c), (a, c, a), (c, a, a). Similarly if b == c there are 3 possible orderings.
Otherwise we have n - 1 possible choices for b satisfying a < b < c, and there are 3! = 6 possible orderings for a, b, c.
Thus for a given n, the number of possible colours satisfying c - a = n is:
(k - n + 1) * (3 + 3 + 6 * (n - 1)) = (k - n + 1) * 6 * n
Summing this over all n <- [1..v] and adding the equal-components case gives a grand total of:
k + 1 + sum [(k - n + 1) * 6 * n | n <- [1..v]]
With a little algebra, we can simplify this formula. The summation can broken into two:
6*(k + 1) * sum[n | n <- [1..v]] - 6*sum[n^2 | n <- [1..v]]
We can apply well-known formulas for the sum of the first v numbers (triangular numbers) and the first v squares (square pyramidal numbers) to get:
6*(k + 1)*v*(v + 1)/2 - 6*v*(v + 1)*(2*v + 1)/6
import Jam main = jam $ getints >>= \[k, v] -> return . show $ k + 1 + v*(v + 1)*(3*k - 2*v + 2)
Haskell’s built-in support for arbitrary-precision arithmetic means the simple approach works: just compute all multifactorials of 9000 and count their digits with length . show.
import Jam import Control.Applicative import Data.List import Data.Maybe fs = length . show . (\e -> product [9000,9000-e..1]) <$> [1..8999] main = jam $ getints >>= \[d] -> return $ if d <= 4 then "..." else "IT'S OVER 9000" ++ replicate (1 + fromJust (findIndex (< d) fs)) '!'
Suppose the first turn happens on the topmost row. Afterwards, it’s as if we’re starting again on a grid with c - 1 rows and r - 1 columns.
Otherwise the topmost row is uninvolved, so we may as well pretend we started on a grid with r - 1 rows and c columns.
Thus if f r c is the number of different paths, we have the recursion
f r c = f (r - 1) c + f (c - 1) (r - 1)
The base cases are simple: if r == 1 or c == 1, then there is only one possible path. By induction, this means f r c == f c r, and in fact the above recursion is describing a sort of off-by-one Pascal’s triangle. We have:
f r c = (r + c - 2) `choose` (r - 1)
It’s easy to compute binomial coefficients ourselves, but we may as well let a library do the hard work:
$ cabal install exact-combinatorics
This library uses a fast method due to Goetgheluck.
import Jam import Math.Combinatorics.Exact.Binomial main = jam $ getints >>= \[r, c] -> return . show . choose (r+c-2) $ r-1