Solution to ACM Asia Regional at Shanghai, 2000, Problem I: Digital Rivers.

> import List(intersperse)

This problem reminds me of ACM ECNA Regional, 2000, Problem B:
Poly-polygonal Numbers.  I will use the same idea and copy some code
from there.

To compute the next number in the river:

> river_next :: Int -> Int
> river_next n = n + sum (digits n)
>   where digits n | n < 10 = [n]
>                  | otherwise = r : digits q
>           where (q,r) = divMod n 10

To create a river from x: (we store x in the second component of each
element)

> river :: Int -> [Int]
> river x = x : river (river_next x)

To merge two infinite lists:

> merge :: Ord a => [a] -> [a] -> [a]
> merge xs@(x:xt) ys@(y:yt) = if x < y then x : merge xt ys
>                             else y : merge xs yt

Find the meeting point between river n and rivers 1,3,9.  Returns
(point, river id).

> rivers139 = foldl1 merge (map (\x -> zip (river x) (repeat x)) [1,3,9])

> meet :: Int -> (Int,Int)
> meet n = firstcontact (river n) rivers139
>   where
>   firstcontact xs@(x:xt) ys@(p@(y,n):yt) | x == y = p
>                                          | x < y  = firstcontact xt ys
>                                          | x > y  = firstcontact xs yt

> main = main' 1
>   where
>   main' c = do n <- readLn
>                if n==0 then return ()
>                   else do let (y,x) = meet n
>                           if c>1 then putStrLn "" else return ()
>                           putStrLn ("Case #" ++ show c)
>                           putStrLn ("first meets river " ++ show x ++
>                                     " at " ++ show y)
>                           main' (c+1)