#include #include // cout, endl, cin #include // string, to_string, stoi #include // vector #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // pair, make_pair #include // tuple, make_tuple #include // int64_t, int*_t #include // printf #include // map #include // queue, priority_queue #include // set #include // stack #include // deque #include // unordered_map #include // unordered_set #include // bitset #include // isupper, islower, isdigit, toupper, tolower #include #include #pragma GCC optimize("Ofast") using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++) typedef long long ll; typedef unsigned long long ull; const ll inf=1e18; using graph = vector > ; using P= pair; using vi=vector; using vvi=vector; using vll=vector; using vvll=vector; using vp=vector

; using vpp=vector; //string T="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //string S="abcdefghijklmnopqrstuvwxyz"; //g++ main.cpp -std=c++14 -I . //cout <> s; reverse(s.begin(),s.end()); int n=s.size(); vi a(n); rep(i,n)a[i]=s[i]-'0'; vvll dp(n+1,vll(2,inf)); dp[0][0]=0; rep(i,n)rep(j,2){ int now=j+a[i]; int nj=now/2; if(now%2==0)dp[i+1][nj]=min(dp[i+1][nj],dp[i][j]); else { dp[i+1][1]=min(dp[i+1][1],dp[i][j]+1); dp[i+1][0]=min(dp[i+1][0],dp[i][j]+1); } } cout << min(dp[n][0],dp[n][1]+1) << endl; }