#line 1 "e.cpp" #include #line 1 "/home/ardririy/repos/cp-libs/libraries-cpp/input.hpp" #line 7 "/home/ardririy/repos/cp-libs/libraries-cpp/input.hpp" using namespace std; vector i64_vec_IN(int n) { vector res(n); for(int i=0; i> res[i]; } return res; } vector str_vec_IN(int n) { vector res(n); for(int i=0; i> res[i]; } return res; } vector> graph_IN(int n, int m) { vector> g(n); int u, v; for(int i=0; i> u >> v; u--; v--; g[u].emplace_back(v); g[v].emplace_back(u); } return g; } #line 3 "e.cpp" using namespace std; // using namespace atcoder; #define all(v) v.begin(),v.end() #define resort(v) sort(v.rbegin(),v.rend()) using ll = long long; using ull = unsigned long long; using vll=vector; using vvll = vector>; using P = pair; using vp=vector>; using djks=priority_queue>; const ll inf=1ll<<60; #define mod10 (ll)1e9+7 #define mod99 (ll)998244353 const double PI = acos(-1); #define rep(i,n) for (ll i=0;i=0;--i) #define rep2(i,a,n) for (ll i=a;i=a;--i) templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> n; string s; cin >> s; vvll dp(n+1, vll(4, inf)); dp[0][3] = 0; // '11'からの続きとして見る rep(i,n) { ll v = s[i]-'0'; rep2(j,1,4) { // cerr << "dp[" << i << "][" << j << "]= " << dp[i][j] << '\n'; if(dp[i][j]==inf) continue; if(__popcount(j) == 1) { int nj = ((j<<1) | 1) & 3; // 1で埋めないとだめ chmin(dp[i+1][nj], dp[i][j] + 1-v); } else { // 1を使う int nj = ((j<<1) | 1) & 3; chmin(dp[i+1][nj], dp[i][j] + 1-v); if(v==0) { nj = (j<<1) & 3; chmin(dp[i+1][nj], dp[i][j]); } } } } ll ans = inf; rep2(i,1,4) chmin(ans, dp[n][i]); cout << ans << '\n'; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t=1; //cin >> t; while(t--)solve(); }