Submission #111861

---

Source Code Expand

import Data.List (permutations)

main :: IO ()
main = do
  ((n:_:_):ms) <- fmap (map (map read . words) . lines) getContents
  print $ solve n $ map (\[a,b] -> (a,b)) ms

solve _ [] = 1
solve n ms = (+) 1 $ maximum $ map (flip f []) $ concatMap permutations ns
    where 
      f [] _      = 0
      f (x:xs) ys = if acqAll x ys ms then 1 + f xs (x:ys) 
                    else f xs ys
      ns = map (\x -> filter (\y -> acq x y ms) [x..n]) [1..n]

acq :: Int -> Int -> [(Int, Int)] -> Bool
acq _ _ [] = False
acq x y ((a,b):cs)
    | x == a && y == b = True
    | x == b && y == a = True
    | otherwise        = acq x y cs

acqAll :: Int -> [Int] -> [(Int, Int)] -> Bool
acqAll _ [] _  = True
acqAll x ys zs = all (\y -> acq x y zs) ys

Submission Info

Judge Result