結果

問題 No.154 市バス
ユーザー AyachiGinAyachiGin
提出日時 2016-06-11 22:44:14
言語 Haskell
(9.8.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 106 ms
7,936 KB
testcase_01 AC 108 ms
7,936 KB
testcase_02 AC 110 ms
8,192 KB
testcase_03 AC 62 ms
8,064 KB
testcase_04 AC 104 ms
7,936 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 97 ms
8,064 KB
testcase_08 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

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