# Code Jam to I/O 2015 for Women

## I/O Error

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').

import Jam
import Control.Applicative
import Data.Char
import Data.List.Split

main = jam $gets >> gets >>= \s -> return$
return . show $k + 1 + v*(v + 1)*(3*k - 2*v + 2) ## Power Levels 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)) '!'

## Googlander

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 import Jam import Math.Combinatorics.Exact.Binomial main = jam$ getints >>= \[r, c] -> return . show . choose (r+c-2) \$ r-1

Ben Lynn blynn@cs.stanford.edu 💡