AtCoder Beginner Contest 283 C問題 Cash Register
問題
提出解答
問題の概要
で初期化された変数
に対して, 「以下の操作のうち1個を選び行う」ことを最低何回行うと
にすることができるか?
以上
以下の整数
を選び,
制約
解法
を文字列とみなす. すると, 問題は次のように言い換えることができる.
空文字で初期化された文字列 が与えられる. 「以下の操作のうち1個を選び行う」ことを最低何回行うと
にすることができるか?
以上
以下の整数
を選び,
の末尾に
を表す数字を追加する.
の末尾に
を追加する.
の中にある
が連続する区間が
個あり, それぞれ,
個連続しているとする.
番目の区間について, 連続する
個の
は次のようにして最短回数で表すことができる.
回末尾に
を追加する.
が奇数ならば, 末尾に
を追加する.
それ以外の数字はその数字を1個ずつ入力するしか方法がない.
以上から, に含まれる
以外の数字の数を
とすると, 答えは
である.