Done several tasks

[cses-programming-tasks.git] / app / cses2431.hs

diff --git a/app/cses2431.hs b/app/cses2431.hs
new file mode 100644 (file)
index 0000000..bebaf9d
--- /dev/null
+++ b/app/cses2431.hs
@@ -0,0 +1,52 @@
+import Data.List
+import Control.Monad
+
+main :: IO ()
+main = do
+  line1 <- getLine
+  let numQuestions = read line1 :: Int
+  answers <- forM [1..numQuestions] $ \_ -> do
+    line <- getLine
+    -- print (">> " ++ line)
+    let question = read line
+    -- print $ ("<> " ++ (show $ skipPlaces question))
+    return $ skipPlaces question
+  putStrLn $ unlines $ map show answers
+
+
+-- lenUpTo, startOf, calcStartOfPiece, calcStartOf :: Integer -> Integer
+-- lenUpTo n = fromIntegral $ length $ mconcat $ map show $ takeWhile (< n) [1..]
+
+-- startOf n = (lenUpTo n) + 1
+
+-- calcStartOfPiece n 
+--   | n < 10 = n
+--   | n < 100 = 2 * (n - 10) + 9 + 1
+--   | n < 1000 = 3 * (n - 100) + (90 * 2) + 9 + 1
+--   | n < 10000 = 4 * (n - 1000) + (900 * 3) + (90 * 2) + 9 + 1
+
+-- calcStartOf n = (k + 1) * (n - 10 ^ k) + smaller
+--   where k = discreteLog n
+--         smaller = 1 + sum [9 * 10 ^ (i - 1) * i | i <- [1..k]]
+
+-- discreteLog :: Integer -> Integer
+-- discreteLog n = go n 0
+--   where go k p
+--           | k < 10 = p
+--           | otherwise = go (k `div` 10) (p + 1)
+
+
+-- cbStart n = (startOf n, calcStartOf n, calcStartOfPiece n)
+
+prefixLengths :: [Integer]
+prefixLengths = scanl' f 0 [1..]
+  where f acc i = acc + 9 * 10 ^ (i - 1) * i
+
+skipPlaces :: Integer -> Integer
+skipPlaces n = read [(show thisNum) !! (fromIntegral(n - (prevNumsLen + lowerOrders + 1)))]
+  where -- k = discreteLog n
+        k = fromIntegral $ (length $ takeWhile (< n) prefixLengths) - 1
+        lowerOrders = prefixLengths !! (fromIntegral k)
+        prevNums = ((n - (lowerOrders + 1)) `div` (k + 1))
+        prevNumsLen = prevNums * (k + 1)
+        thisNum = prevNums + (10 ^ k)