概要
n 個のボタンを備える鍵がある。
この鍵を開けるには、全てのボタンを正しい順序で押さなければならない。
正しい順序でボタンを押している限り、ボタンは押されたままになる。
間違ったボタンを押すと、全てのボタンは押されていない状態に戻る。
全てのボタンが押されている状態になったとき、鍵が開く。
Manao は正しい順序を知らないが、この鍵を開けようとしている。
Manao が最適な戦略を取ることができるとき、最も悪いケースでのボタンを押す回数を求めよ。
解法
- 各段階に於いて、（残っているボタンの数） - 1 回の試行で間違ったボタンを全て調べることができる。
- 全ての間違った順序が試行された後、n 回ボタンを押すと解錠することができる。
これらの条件を元に数え上げると解けます。
コード
import Control.Applicative import Control.Monad import Data.List main = do n <- readLn print $ solve 1 ( n - 1 ) solve :: Integer -> Integer -> Integer solve t 0 = t solve t n = n * t + solve ( t + 1 ) ( n - 1 )
