torus711 のアレ

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

Codeforces #206, Division 2, A : Vasya and Digital Root

概要

関数 S を次のように定める
 S( n ) = n の各桁の和
整数 n に対し、関数 dr を次のように定める。
 dr( n ) = S( n ) ( S( n ) < 10 )
 dr( n ) = dr( S( n ) ) ( otherwise )

二つの整数 k, d が与えられる。
dr( n ) = d となる、Leading Zero をもたない k 桁の整数 n を一つ出力せよ。
存在しない場合は "No solution" と表示せよ。

解法

dr を無理に再帰させる必要は無いので、d を最上位桁にもつ k 桁の数を出力すればよいです。
d = 0 かつ 1 < k のときには解がありません。

コード

main = do
	[ k, d ] <- map read . words <$> getLine
	putStrLn $ if d == 0 && 1 < k
		then "No solution"
		else show d ++ replicate ( k - 1 ) '0'