結果

問題 No.7 プライムナンバーゲーム
ユーザー 3405691582
提出日時 2017-03-21 12:04:47
言語 Haskell
(8.0.2)
結果
AC  
実行時間 2010 ms
コード長 937 Byte
コンパイル時間 1425 ms
使用メモリ 7920 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 4 ms
1888 KB
02.txt AC 3 ms
1912 KB
03.txt AC 1735 ms
7668 KB
04.txt AC 91 ms
3952 KB
05.txt AC 27 ms
3856 KB
06.txt AC 27 ms
3856 KB
07.txt AC 499 ms
5896 KB
08.txt AC 319 ms
4884 KB
09.txt AC 137 ms
4052 KB
10.txt AC 781 ms
5896 KB
system_test1.txt AC 1867 ms
7888 KB
system_test2.txt AC 2010 ms
7660 KB
system_test3.txt AC 1660 ms
7920 KB
テストケース一括ダウンロード

ソースコード

diff #
import qualified Data.Map as M

type Table = M.Map Int Bool

main = do
  n <- read <$> getLine
  putStrLn $ if snd $ battle (primesLeqN n) M.empty n then "Win" else "Lose"

primesLeqN :: Int -> [Int]
primesLeqN n =
  sieve [2..n] where
    sieve [] = []
    sieve (n:ns) = n:sieve [m|m<-ns,mod m n/=0]

{-battle' :: Int -> Bool
battle' n 
  | n <= 1 = True
  | otherwise =
    not $ and $ battle' <$> ((n-) <$> primesLeqN n)-}

battle :: [Int] -> Table -> Int -> (Table,Bool)
battle primes tbl n 
  | n <= 1 = (tbl,True)
  | otherwise =
    case M.lookup n tbl of
      Just b -> (tbl,b)
      Nothing -> (M.insert n (not rslt) tbl',not rslt)
        where
          (tbl',rslt) = battleAux tbl n $ takeWhile (n>) primes
          battleAux tbl n [] = (tbl,True)
          battleAux tbl n (p:ps) = (tbl'',b && rslt')
            where
              (tbl''',b) = battle primes tbl (n-p)
              (tbl'',rslt') = battleAux tbl''' n ps
0