fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // Type Aliases for readability
  6. using ll = long long;
  7.  
  8. /**
  9.  * Calculates the cumulative cost to transform the string based on a target character.
  10.  * @param target: The character we want to process (e.g., '0' or '1')
  11.  * @param s: The input string
  12.  * @param n: String length
  13.  * @return A vector containing the cumulative cost at each position
  14.  */
  15. vector<ll> calculate_costs(char target, const string& s, ll n) {
  16.     vector<ll> costs(n, 0);
  17.     ll current_penalty = 0;
  18.  
  19.     for (ll i = 0; i < n; ++i) {
  20.         // Get the cost from the previous position if it exists
  21.         ll previous_cost = (i > 0) ? costs[i - 1] : 0;
  22.  
  23.         if (s[i] == target) {
  24.             // Logic: if current char matches target, add penalty and reset it
  25.             ll extra_cost = (current_penalty * 2) + 1;
  26.             costs[i] = previous_cost + extra_cost;
  27.             current_penalty = 0;
  28.         } else {
  29.             // Otherwise, increase the penalty for the next match
  30.             current_penalty++;
  31.             costs[i] = previous_cost;
  32.         }
  33.     }
  34.     return costs;
  35. }
  36.  
  37. /**
  38.  * Finds the minimum combined cost from forward and backward passes.
  39.  * Note: Since 'backward' is reversed, we align costs[i] with backward_costs[n-1-i]
  40.  */
  41. ll find_min_combined_cost(const vector<ll>& forward, const vector<ll>& backward, ll n) {
  42.     ll min_total = LLONG_MAX;
  43.  
  44.     for (ll i = 0; i < n; ++i) {
  45.         // Aligning forward index i with its corresponding backward index
  46.         ll combined = forward[i] + backward[n - 1 - i];
  47.         min_total = min(min_total, combined);
  48.     }
  49.     return min_total;
  50. }
  51.  
  52. void solve() {
  53.     ll n;
  54.     if (!(cin >> n)) return;
  55.     string s;
  56.     cin >> s;
  57.  
  58.     // Create a reversed version of the string for backward calculation
  59.     string reversed_s = s;
  60.     reverse(reversed_s.begin(), reversed_s.end());
  61.  
  62.     // Calculate costs for both '0' and '1' in both directions
  63.     vector<ll> forward_zeros = calculate_costs('0', s, n);
  64.     vector<ll> backward_zeros = calculate_costs('0', reversed_s, n);
  65.  
  66.     vector<ll> forward_ones = calculate_costs('1', s, n);
  67.     vector<ll> backward_ones = calculate_costs('1', reversed_s, n);
  68.  
  69.     // Get the minimums for each target character
  70.     ll min_zero_cost = find_min_combined_cost(forward_zeros, backward_zeros, n);
  71.     ll min_one_cost = find_min_combined_cost(forward_ones, backward_ones, n);
  72.  
  73.     // Output the overall minimum
  74.     cout << min(min_zero_cost, min_one_cost) << "\n";
  75. }
  76.  
  77. int main() {
  78.     // Optimization for fast I/O
  79.     ios_base::sync_with_stdio(false);
  80.     cin.tie(NULL);
  81.  
  82.     int test_cases = 1;
  83.     cin >> test_cases;
  84.     while (test_cases--) {
  85.         solve();
  86.     }
  87.     return 0;
  88. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LDA3Uo
language:
C++14 (clang 8.0)
created:
1 hour 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!