torus711 のアレ

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

Codeforces #235, A : Vanya and Cards

問題概要

 それぞれ絶対値が x 以下の整数が一つ書かれたカードが n 枚ある。同様の(絶対値が x 以下の整数が一つ書かれたカード)を複数枚加えて、全てのカードに書かれた値の和を 0 にしたい。最小で何枚のカードが必要か、求めよ。

解法

 絶対値の制約が許す範囲で任意のカードを足せるので、できるだけ絶対値の大きなカードを使って和を 0 に近づけた方が、その後足さなければならない値の絶対値が小さくなって得です。そのような近づけ方をしたとき、必要になるカードの枚数は、和の絶対値を x で整数切り上げ除算した値と等しくなります。

コード

main = do
	[ n, x ] <- map read . words <$> getLine
	s <- abs . sum . map read . words <$> getLine
	print $ ( s + x - 1 ) `div` x