#pragma region Macros #include #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define ALL(v) (v).begin(), (v).end() #define LLA(v) (v).rbegin(), (v).rend() #define SZ(v) (int)(v).size() #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ read(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ read(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define STRING(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) #define VEC2(type, name, height, width) \ vector> name(height, vector(width)); \ read(name) using namespace std; using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template struct edge { int from, to; T cost; edge(int f, int t, T c) : from(f), to(t), cost(c) {} }; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; const char newl = '\n'; template inline vector make_vec(size_t a, T val) { return vector(a, val); } template inline auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } void read() {} template inline void read(T &a) { cin >> a; } template inline void read(pair &p) { read(p.first), read(p.second); } template inline void read(vector &v) { for(auto &&a : v) read(a); } template inline void read(Head &head, Tail &...tail) { read(head), read(tail...); } template void write(const T &a) { cout << a << '\n'; } template void write(const vector &a) { for(int i = 0; i < a.size(); i++) cout << a[i] << (i + 1 == a.size() ? '\n' : ' '); } template void write(const Head &head, const Tail &...tail) { cout << head << ' '; write(tail...); } template void writel(const T &a) { cout << a << '\n'; } template void writel(const vector &a) { for(int i = 0; i < a.size(); i++) cout << a[i] << '\n'; } template void writel(const Head &head, const Tail &...tail) { cout << head << '\n'; write(tail...); } template auto sum(const vector &a) { return accumulate(ALL(a), T(0)); } template auto min(const vector &a) { return *min_element(ALL(a)); } template auto max(const vector &a) { return *max_element(ALL(a)); } template inline void chmax(T &a, T b) { (a < b ? a = b : a); } template inline void chmin(T &a, T b) { (a > b ? a = b : a); } struct IO { IO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); } } io; #pragma endregion int main() { STRING(S); reverse(ALL(S)); int n = S.size(); int j = 0; int res = 0; auto dp = make_vec(n + 1, 2, INF); dp[0][0] = 0; rep(i, n) { if(S[i] == '0') { chmin(dp[i + 1][0], min(dp[i][0], dp[i][1] + 1)); chmin(dp[i + 1][1], dp[i][1] + 1); } else { chmin(dp[i + 1][0], dp[i][0] + 1); chmin(dp[i + 1][1], min(dp[i][0] + 1, dp[i][1])); } } write(min(dp[n][0], dp[n][1] + 1)); }