1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
-- This solves Google Code Jam 2012 Qualification Problem C "Recycled Numbers" [1].
-- The problem is: given a range of numbers with the same number of digits,
-- count how many pairs of them are the same modulo rotation of digits.
--
-- [1]: http://code.google.com/codejam/contest/1460488/dashboard#s=p2
{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad.Trans.Loop
import Control.Applicative ((<$>))
import Control.Monad
import Control.Monad.ST
import Control.Monad.Trans.Class
import Data.Array.ST
import Data.STRef
recycledNumbers :: (Int, Int) -> Int
recycledNumbers (lb, ub)
| not (1 <= lb && lb <= ub && factor == rotateFactor ub)
= error "recycledNumbers: invalid bounds"
| otherwise = runST $ do
bmp <- newArray (lb, ub) False :: ST s (STUArray s Int Bool)
total <- newSTRef 0
forM_ [lb..ub] $ \i -> do
count <- newSTRef 0
foreach (iterate rotate i) $ \j -> do
when (not $ j >= i && j <= ub)
continue
whenM (lift $ readArray bmp j)
exit
lift $ writeArray bmp j True
lift $ modifySTRef' count (+1)
readSTRef count >>= modifySTRef' total . (+) . numPairs
readSTRef total
where
factor = rotateFactor lb
rotate x = let (n, d) = x `divMod` 10
in d*factor + n
numPairs n = (n-1) * n `div` 2
main :: IO ()
main = do
t <- readLn
forM_ [1..t] $ \(x :: Int) -> do
[a, b] <- map read . words <$> getLine
let y = recycledNumbers (a, b)
putStrLn $ "Case #" ++ show x ++ ": " ++ show y
------------------------------------------------------------------------
-- Helper functions
-- | Return the power of 10 corresponding to the most significant digit in the
-- number.
rotateFactor :: Int -> Int
rotateFactor n | n < 1 = error "rotateFactor: n < 1"
| otherwise = loop 1
where
loop p | p' > n = p
| p' < p = p -- in case of overflow
| otherwise = loop p'
where p' = p * 10
modifySTRef' :: STRef s a -> (a -> a) -> ST s ()
modifySTRef' ref f = do
x <- readSTRef ref
writeSTRef ref $! f x
whenM :: Monad m => m Bool -> m () -> m ()
whenM p m = p >>= \b -> if b then m else return ()
|
