fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int t; 
  9.     cin >> t;
  10.     while (t--) {
  11.         int n;
  12.         string s;
  13.         cin >> n >> s;
  14.  
  15.         if (n == 1) {
  16.             // Only one char: 
  17.             // press = 1, plus move if it's '1'
  18.             cout << 1 + (s[0]=='1') << "\n";
  19.             continue;
  20.         }
  21.  
  22.         int T01 = 0, T10 = 0;
  23.         for (int i = 0; i+1 < n; i++) {
  24.             if      (s[i]=='0' && s[i+1]=='1') T01++;
  25.             else if (s[i]=='1' && s[i+1]=='0') T10++;
  26.         }
  27.         int trans = T01 + T10;
  28.         int start = (s[0]=='1');
  29.  
  30.         // How many moves can we cut out?
  31.         int best_delta = 0;
  32.  
  33.         // (A) Cut 2 if possible:
  34.         if (T01 >= 2 || T10 >= 2) {
  35.             best_delta = 2;
  36.         } else if (s[0]=='1' && T01 >= 1) {
  37.             // flip the very first '1'→'0' _and_ collapse one 0→1
  38.             best_delta = 2;
  39.         }
  40.  
  41.         // (B) Otherwise, maybe cut 1:
  42.         if (best_delta == 0) {
  43.             // 1) merge one internal boundary against the end
  44.             bool boundary1 = false;
  45.             for (int i = 0; i+1 < n; i++) {
  46.                 if (s[i] != s[i+1] && s[i] == s[n-1]) {
  47.                     boundary1 = true;
  48.                     break;
  49.                 }
  50.             }
  51.             // 2) flip only the very first move by reversing a prefix that ends
  52.             //    in a '0' (so start 1→0) without introducing a new boundary
  53.             bool flip_start = (s[0]=='1' && s[n-1]=='0');
  54.  
  55.             if (boundary1 || flip_start)
  56.                 best_delta = 1;
  57.         }
  58.  
  59.         int ans = n + start + trans - best_delta;
  60.         cout << ans << "\n";
  61.     }
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
3
000
3
111
3
011
3
100
5
10101
19
1101010010011011100
stdout
copy 
3
4
4
4
8
29
https://ideone.com/pWT3z1
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!