Submission #25081

---

Source Code Expand

import Data.Maybe (catMaybes)
import qualified Data.Attoparsec.ByteString.Char8 as P
import qualified Data.ByteString as BS

{- | 愚直な解法

>>> solve 4 3
[(3,2)]
-}
solve :: Integer -> Integer -> [(Integer,Integer)]
solve x y = ns
  where
    ns = takeWhile (\(x,y) -> y <= x) $ catMaybes $ do
      n <- [n_min..]
      let nn = (1 + n) * n `div` 2
      let (o,d) = (x * n) `divMod` y
      return $ if d == 0 && nn > o
               then Just (n, nn - o) else Nothing
    n_min = (y + 2 * x) `div` y


main :: IO ()
main = do
  (P.Done _ (x,y)) <- BS.getContents >>= return . P.parse myparser
  let ans = solve x y
  if ans == []
    then putStrLn "Impossible"
    else mapM_ (\(n,m) -> putStrLn $ show n ++ " " ++ show m) ans
  where
    myparser = do { x <- P.decimal; P.char '/'; y <- P.decimal; return (x,y) }

Submission Info

Judge Result