Submission #992212
Source Code Expand
{-# LANGUAGE ScopedTypeVariables #-} import Control.Applicative import Control.Monad import Control.Monad.State import Control.DeepSeq import Data.Array import Data.Bits import Data.Char import Data.Functor.Identity import Data.List import Data.Maybe import Data.Ord import Data.Tree import Data.Tuple import qualified System.IO import qualified Data.Map as M import qualified Data.Set as S import qualified Data.Sequence as Q import qualified Data.ByteString.Char8 as B main = do [n,a] <- getInts print $ minimum $ map (solve n a) [1..4*12] solve :: Z->Z->Z->Z solve n a c = let b0 = floor $ (fint n + 0.5) ** (1 / fint c) b1 = b0+1 m0 = head [m | (m,bs) <- zip [0..] $ iterate (\ x -> (x`div`b0) * b1) (b0^c), bs >= n] in b0*(c-m0) + b1*m0 + a*(c-1) type Z = Int type Q = Rational type R = Double type S = String fint :: (Integral a, Num b) => a -> b fint = fromIntegral getInt = fst . fromJust . B.readInt <$> B.getLine getIntPair = (\[a,b]->(a,b)) <$> getInts getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine getStr = B.unpack <$> B.getLine yesNo :: Bool -> String yesNo True = "Yes" yesNo False = "No" printList :: (Show a) => [a] -> IO () printList = putStrLn . unwords . map show readLnList :: (Read a) => IO [a] readLnList = map read . words <$> getLine ----- Union-find type UnionFindT v m a = StateT (M.Map v (UnionFindVal v)) m a newtype UnionFindVal v = UnionFindVal v runUnionFindT :: (Monad m) => UnionFindT v m a -> m a runUnionFindT = flip evalStateT $ M.empty runUnionFind = runIdentity . runUnionFindT ufFresh :: (Monad m, Ord v) => v -> UnionFindT v m () ufFresh v = modify $ M.insert v (UnionFindVal v) ufClass :: (Monad m, Ord v) => v -> UnionFindT v m v ufClass v = do (UnionFindVal pv) <- gets (M.! v) if v == pv then return v else do c <- ufClass pv modify $ M.insert v (UnionFindVal c) return c ufUnify v w = do cv <- ufClass v cw <- ufClass w modify $ M.insert cw (UnionFindVal cv) return $ cv /= cw
Submission Info
Submission Time | |
---|---|
Task | E - Cookies |
User | tos |
Language | Haskell (GHC 7.10.3) |
Score | 1000 |
Code Size | 2095 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 636 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
dataset1 | sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt |
dataset2 | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, 02-33.txt, 02-34.txt, 02-35.txt, 02-36.txt, 02-37.txt, 02-38.txt, 02-39.txt, 02-40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 5 ms | 636 KB |
01-02.txt | AC | 3 ms | 508 KB |
01-03.txt | AC | 3 ms | 508 KB |
01-04.txt | AC | 3 ms | 508 KB |
01-05.txt | AC | 3 ms | 508 KB |
01-06.txt | AC | 3 ms | 508 KB |
01-07.txt | AC | 3 ms | 508 KB |
01-08.txt | AC | 3 ms | 508 KB |
01-09.txt | AC | 3 ms | 508 KB |
01-10.txt | AC | 3 ms | 508 KB |
01-11.txt | AC | 3 ms | 508 KB |
01-12.txt | AC | 3 ms | 508 KB |
01-13.txt | AC | 3 ms | 508 KB |
01-14.txt | AC | 3 ms | 508 KB |
01-15.txt | AC | 3 ms | 508 KB |
01-16.txt | AC | 3 ms | 508 KB |
01-17.txt | AC | 3 ms | 508 KB |
01-18.txt | AC | 3 ms | 508 KB |
01-19.txt | AC | 3 ms | 508 KB |
01-20.txt | AC | 3 ms | 508 KB |
01-21.txt | AC | 3 ms | 380 KB |
01-22.txt | AC | 3 ms | 380 KB |
01-23.txt | AC | 3 ms | 508 KB |
01-24.txt | AC | 3 ms | 508 KB |
01-25.txt | AC | 3 ms | 508 KB |
01-26.txt | AC | 3 ms | 508 KB |
02-01.txt | AC | 3 ms | 380 KB |
02-02.txt | AC | 3 ms | 508 KB |
02-03.txt | AC | 3 ms | 508 KB |
02-04.txt | AC | 3 ms | 508 KB |
02-05.txt | AC | 3 ms | 508 KB |
02-06.txt | AC | 3 ms | 508 KB |
02-07.txt | AC | 3 ms | 508 KB |
02-08.txt | AC | 3 ms | 508 KB |
02-09.txt | AC | 3 ms | 508 KB |
02-10.txt | AC | 3 ms | 508 KB |
02-11.txt | AC | 3 ms | 508 KB |
02-12.txt | AC | 3 ms | 508 KB |
02-13.txt | AC | 3 ms | 508 KB |
02-14.txt | AC | 3 ms | 508 KB |
02-15.txt | AC | 3 ms | 508 KB |
02-16.txt | AC | 3 ms | 508 KB |
02-17.txt | AC | 3 ms | 508 KB |
02-18.txt | AC | 3 ms | 508 KB |
02-19.txt | AC | 3 ms | 508 KB |
02-20.txt | AC | 3 ms | 508 KB |
02-21.txt | AC | 3 ms | 508 KB |
02-22.txt | AC | 3 ms | 508 KB |
02-23.txt | AC | 3 ms | 508 KB |
02-24.txt | AC | 3 ms | 508 KB |
02-25.txt | AC | 3 ms | 508 KB |
02-26.txt | AC | 3 ms | 508 KB |
02-27.txt | AC | 3 ms | 508 KB |
02-28.txt | AC | 3 ms | 508 KB |
02-29.txt | AC | 3 ms | 508 KB |
02-30.txt | AC | 3 ms | 508 KB |
02-31.txt | AC | 3 ms | 508 KB |
02-32.txt | AC | 3 ms | 508 KB |
02-33.txt | AC | 3 ms | 508 KB |
02-34.txt | AC | 3 ms | 508 KB |
02-35.txt | AC | 3 ms | 508 KB |
02-36.txt | AC | 3 ms | 508 KB |
02-37.txt | AC | 3 ms | 508 KB |
02-38.txt | AC | 3 ms | 508 KB |
02-39.txt | AC | 3 ms | 508 KB |
02-40.txt | AC | 3 ms | 508 KB |
sample-01.txt | AC | 3 ms | 508 KB |
sample-02.txt | AC | 3 ms | 508 KB |
sample-03.txt | AC | 3 ms | 508 KB |