Official
C - Cash Register Editorial by MMNMM
\(S\) をレジに入力するために必要なボタン入力の回数を \(f(S)\) と書くことにします。
すると、最後に入力するボタンについて考えることで、\(f(S)\) は次のように再帰的に求めることができます。
- \(f(S)=0\phantom{f(\lfloor S/100\rfloor)+}\quad(S=0)\)
- \(f(S)=f(S/100)+1\phantom{\lfloor\rfloor}\quad(S\equiv0\pmod{100})\)
- \(f(S)=f(\left\lfloor S/10\right\rfloor)+1\phantom{0}\quad(\)それ以外\()\)
これが正しいことは、0
と 00
を連続して入力する場合にこれらを入れ替えてもよいことを使って示すことができます。
あとは、この式に従って計算を行えばよいです。 このような形の再帰関数は while 文などを用いたシンプルな繰り返しで計算することができます(もちろん再帰関数として計算することもできます)。
この問題では \(S\) が非常に大きく、\(S\) を \(10,100\) で割ることを繰り返すため、\(S\) を十進法で表した文字列で管理すると効率がよいです。
実装例は以下のようになります。
#include <iostream>
#include <string>
int main() {
using namespace std;
string S;
cin >> S;
int ans = 0;
while (!empty(S)) {
const auto back{S.back()};
S.pop_back();
if (back == '0' && S.back() == '0')
// S が 100 の倍数なら、さらに 1 文字消す
S.pop_back();
++ans;
}
cout << ans << endl;
return 0;
}
posted:
last update: