This problem requires counting the number of zeros between the first and last occurrence of 1 in an array.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    int firstOne = -1, lastOne = -1;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (arr[i] == 1) {
            if (firstOne == -1) firstOne = i;
            lastOne = i;
        }
    }
    
    if (firstOne == -1) {
        cout << 0 << '\n';
        return;
    }
    
    int zeroCount = 0;
    for (int i = firstOne + 1; i < lastOne; i++) {
        if (arr[i] == 0) zeroCount++;
    }
    
    cout << zeroCount << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int queries;
    cin >> queries;
    while (queries--) {
        solve();
    }
    return 0;
}

Problem B: Monster Battle Strategy

This problem involves determining if monsters can be defeated by attacking from closest to farthest, using a greedy approach with prefix sums.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Monster {
    ll health;
    ll position;
};

void solve() {
    ll monsterCount, attackPower;
    cin >> monsterCount >> attackPower;
    
    vector<ll> healths(monsterCount);
    vector<ll> positions(monsterCount);
    
    for (int i = 0; i < monsterCount; i++) {
        cin >> healths[i];
    }
    
    for (int i = 0; i < monsterCount; i++) {
        cin >> positions[i];
        positions[i] = abs(positions[i]);
    }
    
    vector<Monster> monsters;
    for (int i = 0; i < monsterCount; i++) {
        monsters.push_back({healths[i], positions[i]});
    }
    
    sort(monsters.begin(), monsters.end(), [](const Monster& a, const Monster& b) {
        return a.position < b.position;
    });
    
    ll cumulativeHealth = 0;
    bool possible = true;
    
    for (const auto& monster : monsters) {
        cumulativeHealth += monster.health;
        if (cumulativeHealth > monster.position * attackPower) {
            possible = false;
            break;
        }
    }
    
    cout << (possible ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

Problem C: String Trensformation

This problem deals with transforming strings based on specific rules and determining if a transformation is possible.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    
    vector<ll> prefixSum(n + 1, 0);
    vector<ll> zeroCount(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + (s[i] - '0');
        zeroCount[i + 1] = zeroCount[i] + (s[i] == '0' ? 1 : 0);
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        
        if (l == r) {
            cout << "YES\n";
            continue;
        }
        
        ll totalDigits = r - l + 1;
        ll ones = prefixSum[r + 1] - prefixSum[l];
        ll zeros = zeroCount[r + 1] - zeroCount[l];
        
        // Check if the transformation is possible
        if (ones >= 4 && (ones - 4) * 2 <= totalDigits) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

Problem D: Binary Search with Prefix Sums

This problem requires finding the minimum number of operations to transform an array using preprocessing and binary search with prefix sums.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = (1ll << 60);

void solve() {
    int n;
    cin >> n;
    vector<ll> arr(n), result(n, INF);
    vector<ll> prefix(n + 1, 0);
    vector<ll> lastDiff(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];
    }
    
    // Preprocess last different position
    for (int i = 1; i <= n; i++) {
        lastDiff[i] = (arr[i - 1] == arr[i - 2]) ? lastDiff[i - 1] : i - 1;
    }
    
    // Left to right pass
    for (int i = 0; i < n; i++) {
        if (i > 0 && arr[i] < arr[i - 1]) {
            result[i] = 1;
            continue;
        }
        
        ll left = 0, right = lastDiff[i + 1];
        while (left <= right) {
            ll mid = (left + right) / 2;
            ll sum = prefix[i + 1] - prefix[mid];
            if (sum > arr[i]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (left <= i) {
            result[i] = min(result[i], i - left + 1);
        }
        if (right >= 0) {
            result[i] = min(result[i], i - right);
        }
    }
    
    // Right to left pass
    reverse(arr.begin(), arr.end());
    for (int i = 0; i <= n; i++) {
        prefix[i] = 0;
        lastDiff[i] = 0;
    }
    
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
    
    for (int i = 1; i <= n; i++) {
        lastDiff[i] = (arr[i - 1] == arr[i - 2]) ? lastDiff[i - 1] : i - 1;
    }
    
    for (int i = 0; i < n; i++) {
        if (i > 0 && arr[i] < arr[i - 1]) {
            result[n - i - 1] = min(result[n - i - 1], 1ll);
            continue;
        }
        
        ll left = 0, right = lastDiff[i + 1];
        while (left <= right) {
            ll mid = (left + right) / 2;
            ll sum = prefix[i + 1] - prefix[mid];
            if (sum > arr[i]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (left <= i) {
            result[n - i - 1] = min(result[n - i - 1], i - left + 1);
        }
        if (right >= 0) {
            result[n - i - 1] = min(result[n - i - 1], i - right);
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << (result[i] == INF ? -1 : result[i]) << " ";
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}