import Jam import Data.Bool main = jam $ do [n, k] <- getints pure $ bool "OFF" "ON" $ (k + 1) `mod` 2^n == 0

# 2010 Qualification Round

## Snapper Chain

After trying a few examples, we realize the chain of *Snappers* is a binary
counter. The light bulb is on if and only if all `n`

bits are one, which
happens every `2^n`

iterations, when the coutner reads `2^n - 1`

:

For this problem, it may be better to head straight to a smart solution. Writing a brute force simulation means we have to simulate a binary counter:

import Jam import Data.Bool main = jam $ do [n, k] <- getints pure $ bool "OFF" "ON" $ and $ iterate snap (replicate n False)!!k snap [] = [] snap (x:xs) = (x /= and xs) : snap xs

## Fair Warning

The GCD of two numbers divides their difference. The difference between any two
times is unaffected by adjusting both by the same offset, thus we simply take
the GCD `d`

of all the differences between all pairs of times, then calculate
how fare we are from the next multiple of `d`

:

import Jam import Data.List main = jam $ do (_:ts) <- getintegers let d = foldl1' gcd $ (-) <$> ts <*> ts pure $ show $ (d - head ts) `mod` d

We take advantage of built-in arbitrary precision arithmetic in Haskell.

We’ve wastefully computed the difference for both orderings of every pair, as well as the difference between every time and itself, but this factor of 2 is unimportant even for the large input.

## Theme Park

We simulate each ride to solve the small input.

If everyone in the queue can fit in the roller coaster, then the problem is
simple. Otherwise, the `cycle`

function fits nicely with the way people rejoin
the queue, and calling `scanl1 (+)`

on the queue gives a cumulative sum.of the
number of people who have ridden the roller coaster so far.

We break this list into chunks such that each chunk is as large as
possible and that the cumulative sum at the end of one chunk differs from
cumulative sum at the end of the previous chunk by at most `k`

.

Then we simply print the cumulative sum at the end of `r`th piece.

We `zip`

a list to a displaced version of itself to give us handy access to
the previous chunk’s cumulative sum:

import Data.List import Jam main = jam $ do [r, k, _] <- getints gs <- getints let csum = scanl1 (+) $ cycle gs f q = dropWhile ((<= snd (head q) + k) . fst) q brute = snd . head $ iterate f (zip csum (0:csum))!!r pure $ show $ if sum gs <= k then r * sum gs else brute

For the large input, we memoize: before each ride, we record the group at the
front of the queue, the number of times `i0`

the roller coaster has run, and
number of people ```
t0`who have ridden so far. Then just before the `i`th run,
if we see the same group at the front of the queue again, and there have been
`t
```

total people who have ridden the coaster so far, we compute:

(quot, rem) = divMod (r - i0) (i - i0)

and fast-forward by `quot * (i - i0)`

runs, that is, with `rem`

runs remaining,
the total number of people who have been on the roller coaster so far is:

t0 + (t - t0) * quot

We use brute force simulation for the remaining `rem`

runs.

To recognize a group we’ve seen before, we label them `[0..n - 1]`

and `zip`

the labels to the cumulative sums. For fun, we use `const`

to generate the
right number of labels, rather than rely on the `n`

given in the input, which
we ignore completely.

import Data.List import qualified Data.Map as M import Jam main = jam $ do [r, k, _] <- getints gs <- getints let step q = dropWhile ((<= snd (head q) + k) . fst) q csum = scanl1 (+) $ cycle gs f m i xs@(x:_) | snd x `M.member` m = t0 + (t - t0) * quot + snd (head $ iterate step (fst <$> xs)!!rem) - t | otherwise = f m' (i + 1) $ dropWhile ((<= t + k) . fst . fst) xs where m' = M.insert (snd x) (i, t) m t = snd $ fst x (i0, t0) = m M.! snd x (quot, rem) = divMod (r - i0) (i - i0) pure $ show $ if sum gs <= k then r * sum gs else f M.empty 0 $ zip (zip csum $ 0:csum) $ cycle $ zipWith const [0..] gs

*blynn@cs.stanford.edu*💡