読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #205, A : Domino

概要

N 枚の板があり、両面に 1 〜 6 のいずれかの数が書かれている。
板に対して裏返す操作ができる。
それぞれの面の数の和をどちらも偶数にするために、裏返さなければならない板の数を求めよ。
不可能な場合は -1 で示せ。

解法

それぞれの面の和について、その奇偶で場合分けをすると次のようになります。

  • ( even, even ) : もうできてる
  • ( odd, odd ) : 片面のみ奇数な板を一枚裏返す。そのような板が無ければ無理
  • それ以外 : 無理

コード

main = do
	n <- readLn
	ps <- replicateM n $ do
		[ a, b ] <- map read . words <$> getLine
		return ( a, b )
	print $ solve ps

solve ps
	| sum1 `mod` 2 == 0 && sum2 `mod` 2 == 0 = 0
	| sum1 `mod` 2 == 1 && sum2 `mod` 2 == 1 =
		if any ( uncurry (&&) . ( even *** odd ) ) ps || any ( uncurry (&&) . ( odd *** even ) ) ps
			then 1
			else -1
	| otherwise = -1
		where
			sum1 = sum . map fst $ ps
			sum2 = sum . map snd $ ps