結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 3 ms
1888 KB
02.txt AC 3 ms
1908 KB
03.txt AC 1704 ms
7664 KB
04.txt AC 93 ms
3952 KB
05.txt AC 28 ms
3852 KB
06.txt AC 28 ms
3856 KB
07.txt AC 521 ms
5904 KB
08.txt AC 351 ms
5908 KB
09.txt AC 142 ms
4072 KB
10.txt AC 822 ms
5908 KB
system_test1.txt AC 1988 ms
7876 KB
system_test2.txt AC 1905 ms
7664 KB
system_test3.txt AC 1730 ms
7924 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