app/cses2431.hs

   1 import Data.List
   2 import Control.Monad
   3
   4 main :: IO ()
   5 main = do
   6   line1 <- getLine
   7   let numQuestions = read line1 :: Int
   8   answers <- forM [1..numQuestions] $ \_ -> do
   9     line <- getLine
  10     -- print (">> " ++ line)
  11     let question = read line
  12     -- print $ ("<> " ++ (show $ skipPlaces question))
  13     return $ skipPlaces question
  14   putStrLn $ unlines $ map show answers
  15
  16
  17 -- lenUpTo, startOf, calcStartOfPiece, calcStartOf :: Integer -> Integer
  18 -- lenUpTo n = fromIntegral $ length $ mconcat $ map show $ takeWhile (< n) [1..]
  19
  20 -- startOf n = (lenUpTo n) + 1
  21
  22 -- calcStartOfPiece n
  23 --   | n < 10 = n
  24 --   | n < 100 = 2 * (n - 10) + 9 + 1
  25 --   | n < 1000 = 3 * (n - 100) + (90 * 2) + 9 + 1
  26 --   | n < 10000 = 4 * (n - 1000) + (900 * 3) + (90 * 2) + 9 + 1
  27
  28 -- calcStartOf n = (k + 1) * (n - 10 ^ k) + smaller
  29 --   where k = discreteLog n
  30 --         smaller = 1 + sum [9 * 10 ^ (i - 1) * i | i <- [1..k]]
  31
  32 -- discreteLog :: Integer -> Integer
  33 -- discreteLog n = go n 0
  34 --   where go k p
  35 --           | k < 10 = p
  36 --           | otherwise = go (k `div` 10) (p + 1)
  37
  38
  39 -- cbStart n = (startOf n, calcStartOf n, calcStartOfPiece n)
  40
  41 prefixLengths :: [Integer]
  42 prefixLengths = scanl' f 0 [1..]
  43   where f acc i = acc + 9 * 10 ^ (i - 1) * i
  44
  45 skipPlaces :: Integer -> Integer
  46 skipPlaces n = read [(show thisNum) !! (fromIntegral(n - (prevNumsLen + lowerOrders + 1)))]
  47   where -- k = discreteLog n
  48         k = fromIntegral $ (length $ takeWhile (< n) prefixLengths) - 1
  49         lowerOrders = prefixLengths !! (fromIntegral k)
  50         prevNums = ((n - (lowerOrders + 1)) `div` (k + 1))
  51         prevNumsLen = prevNums * (k + 1)
  52         thisNum = prevNums + (10 ^ k)