結果

問題 No.154 市バス
コンテスト
ユーザー AyachiGin
提出日時 2016-06-11 22:44:14
言語 Haskell
(9.10.1)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 2,511 bytes
コンパイル時間 1,895 ms
コンパイル使用メモリ 172,544 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-10-13 08:26:18
合計ジャッジ時間 3,127 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff #
raw source code 

module Main where

main :: IO ()
main = do
  i <- readLn
  s <- getContents
  mapM_ (putStrLn . isPossible) . take i . lines $ s

-- | tests
-- >>> isPossible "WWWWWWWWWGR"
-- "possible"
-- >>> isPossible "WWWWGWWWGRR"
-- "possible"
-- >>> isPossible "WWWWWWWWWWWWWWGRRG"
-- "impossible"
-- >>> isPossible "WGRWGR"
-- "possible"
-- >>> isPossible "WWWWWWWWWWWWWWWWWGGWGWGGWGWGGGWGG"
-- "impossible"
-- >>> isPossible "WGWR"
-- "impossible"
-- >>> isPossible "WGRW"
-- "impossible"
-- >>> isPossible "WWWGRGWR"
-- "impossible"
-- >>> isPossible "WWWGGWRR"
-- "impossible"
-- >>> isPossible "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWGWWWWGWWGWWWWWWWWWWWWWGWWWWWWWRWWWWWGGWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWGGWWWGWGWRWWWWWWWWGWWRWWWWWWWWWWWGWWWWRWWWWWRWWWWWWWWWGWWGWWWWWGWWRWGWWWWWGWRWWWGWGWWWGWWGWWGWWWWWWWWWRWGRWGWWWRGGWRWRWGWRWWWRGGGWWWGGWWWWWWWWWWWWWWGWWWGGWGWWWWWWWWWWWWWGWRWGGGGWWRRWWWWWGWGWWWGGWWRWWWGWWWWGWGWGWGRGRRGWRGRGGGWGWGWGWWRRGWRWWWRGWGGWRWWWWWGRGWGWGGWWWGRRRRWWWRWWWRGWWRGGWGWWWWGRWWWWWGGRRWWGRGWGGRWRGWGGWWGWGWGWGWGRWRGWWWGWGWWRRWGWRWWWGWRWGWGWWWWGGRRRWRGRWGGGWRRGGGWWWRGRRWRWWGWWRWWWWWWRWGWRRGWGRRGRWWWGGWWRGRWWRGGRWWGGWWWRRGRRGGRWWGRWRGRWGGRWWGGWGGWGRRWRWWWGRWRGWRRWWGGRWWWRGRGWRGRWWWWWWRGRGWGWWRRRGRGRGGWGWGRGRGRGGWGWGWGWRGRWRGGGGGGRGRRRWWGRGRRGRGWWRRGWWGRRGGGWRRGWGRWRGRGRWRRWRGRWRRGRRWGRWGGGGRRGRRWRRGGGRWWRRRGGGRWWRGGRGGGWRWRRGRRRRGRWRWRRRGRRWGRGRGGRRRGGRWWGRGWWRGRGRGWRWRRRGGRGRGGRWWRRWGRWRRRRWRWRRRRRRWWRRGGRRRWRRRGWRWGWWRGGRRRWRWRRWGRWGWWWGGRWWRRGRWGWGWRGGRGWRRGRGRRWGRGGRWRWRGGGGRRRRGRGRRRRGWRGWGGWGRRWRGWRRRRGWRRWRRGRGGRRRGRRWWRRRWGGRR"
-- "possible"
isPossible :: String -> String
isPossible s = if solve s then
                 "possible"
               else
                 "impossible"
  where
    solve xs = countWGR (0, 0, 0) xs && countRGW (0, 0, 0) (reverse xs)
countWGR (w, g, r) "" = w >= 0 && g == 0 && r >= 1
countWGR (w, g, r) (x:xs)
  | w < 0 || g < 0 = False
  | otherwise      = case x of
                      'W' -> countWGR (w+1, g, r) xs
                      'G' -> countWGR (w-1, g+1, r) xs
                      'R' -> countWGR (w, g-1, r+1) xs
countRGW (r, g, w) "" = g >= 0 && r == 0
countRGW rgw@(r, g, w) (x:xs)
  | g < 0 || r < 0 = False
  | otherwise      = case x of
                      'R' -> countRGW (r+1, g, w) xs
                      'G' -> countRGW (r-1, g+1, w) xs
                      'W' -> countRGW (r, g-1, w+1) xs'
  where
    xs' = let (gx, gy) = break (=='G') xs
          in filter (/='W') gx ++ gy
0