結果

問題 No.7 プライムナンバーゲーム
ユーザー okaduki
提出日時 2016-05-05 00:42:29
言語 Haskell
(9.10.1)
結果
AC  
実行時間 2,053 ms / 5,000 ms
コード長 1,708 bytes
コンパイル時間 1,932 ms
コンパイル使用メモリ 173,824 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2024-10-01 15:46:02
合計ジャッジ時間 17,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:31:12: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Prelude, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
31 |     bits = tail . reverse . map (`mod` 2) . takeWhile (>0) . iterate (`div` 2)
   |            ^^^^
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Text.Printf
import Debug.Trace

class MemoIx a where
  index :: a -> Integer
  unindex :: Integer -> a
instance MemoIx Integer where
  index n | n >= 0 = n*2
          | otherwise = -n*2-1
  unindex n | n `mod` 2 == 0 = n `div` 2
            | otherwise = -((n+1) `div` 2)
instance (MemoIx a, MemoIx b) => MemoIx (a,b) where
  index (a,b) = l*(l+1) `div`2 + ib
    where
      ia = index a
      ib = index b
      l = ia+ib
  unindex ix = (unindex ia, unindex ib)
    where
      l = floor ((-1 + sqrt (1+8*fromIntegral ix))/2)
      ib = ix - l*(l+1) `div` 2
      ia = l - ib
data Tree a = Tree a (Tree a) (Tree a)
findTree :: MemoIx a => Tree b -> a -> b
findTree tree ix = f (bits $ index ix + 1) tree
  where
    bits = tail . reverse . map (`mod` 2) . takeWhile (>0) . iterate (`div` 2)
    f [] (Tree v _ _) = v
    f (0:bs) (Tree _ l _) = f bs l
    f (1:bs) (Tree _ _ r) = f bs r
genTree :: MemoIx a => (a -> b) -> Tree b
genTree f = gen 0
  where
    gen i = Tree (f $ unindex i) (gen (i*2+1)) (gen (i*2+2))
memofix :: MemoIx a => ((a -> b) -> (a -> b)) -> (a -> b)
memofix f = memof where
  memof = f $ findTree tbl
  tbl = genTree memof
memo :: MemoIx a => (a -> b) -> a -> b
memo f = findTree (genTree f)

primes = it [2..10000]
  where
    it [] = []
    it (x:xs) = (x:) $ it $ filter (\a -> a`mod`x /= 0) xs

iswin = memo f
  where
    f x | x <= 3 = False
        | otherwise =
            not $ and $ map (iswin . (\p -> x-p)) $ takeWhile (<=x-2) primes

answer n = if iswin n then "Win" else "Lose"

main = do
  n <- readLn :: IO Integer
  putStrLn $ answer n
0