Let \(f(S)\) be the number of types required to enter \(S\).

Then \(f(S)\) can be found recursively, considering the last button to press:

• \(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(\)otherwise\()\).

This is true because consecutively typing 0 and 00 commutes.

All that left is to find the answer according to this equation. A recursive function in such a form can be found with a simple loop using a while statement for instance. (Of course, you may define a recursive function.)

Since \(S\) is exceptionally large in this problem and we try to repeatedly divide \(S\) by \(10\) and \(100\), one can efficiently process by managing \(S\) as a decimal string.

The following is a sample code.

#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')
            // Remove one more character if S is a multiple of 100
            S.pop_back();
        ++ans;
    }
    cout << ans << endl;

    return 0;
}