torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Regular Contest #011, A : 鉛筆リサイクルの新技術

概要

m 本の使用済み鉛筆から n 本の鉛筆を生成する技術がある。
最初に N 本の鉛筆を販売し、その後全て回収され再生成するプロセスを経るとして、合計何本の鉛筆が販売されるか求めよ。

解法

制約より、完全な鉛筆の数は一回毎に減っていきます。
N がさほど大きくないので、愚直にシミュレーションすることで解けます。

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	[ m, n, ln ] <- map read . words <$> getLine
	let
		res = ln + solve m n ln
	print res

solve :: Int -> Int -> Int -> Int
solve m n rest
	| rest < m = 0
	| otherwise = new + solve m n ( new + rest `mod` m )
		where new = rest `div` m * n