Làm cách nào để giải quyết vấn đề này cho tất cả các ràng buộc

Nông dân John có N con bò trong một hàng (1 Ban đầu, một số con bò bắt đầu bị nhiễm bệnh. Mỗi đêm có bò bệnh truyền bệnh cho các con bò bên trái và bên phải (nếu có). Một khi con bò bị nhiễm bệnh, nó vẫn bị nhiễm bệnh.
Sau vài đêm, nông dân John nhận ra rằng vấn đề đã vượt quá tầm kiểm soát nên ông đã kiểm tra đàn bò của mình để xác định xem con nào mắc bệnh. Tìm số bò ít nhất có thể bị bệnh.
ĐẦU VÀO:
Dòng đầu tiên chứa N, số lượng bò mà nông dân John có.
Dòng tiếp theo chứa chuỗi bit ký tự N chỉ có 1 và 0, trong đó số 1 đại diện cho một con bò bị nhiễm bệnh và số 0 đại diện cho một con bò không bị nhiễm bệnh sau một số đêm.
ĐẦU RA:
Xuất ra một số nguyên duy nhất: số lượng bò tối thiểu có thể bắt đầu bị bệnh.
ĐẦU VÀO MẪU:
5
11111

ĐẦU RA MẪU:
1

Giả sử con bò ở giữa là con bò duy nhất bắt đầu bị nhiễm bệnh. Sau đó bò sẽ bị nhiễm bệnh theo thứ tự sau:
0 đêm: 00100 (con bò thứ 3 bị nhiễm bệnh ban đầu)
1 đêm: -> 01110 (bò thứ 2 và thứ 4 hiện đã nhiễm bệnh)
2 đêm: -> 11111 (con bò thứ nhất và thứ năm hiện đã nhiễm bệnh)
3 đêm: -> 11111 (tất cả bò đều đã nhiễm bệnh nên không còn con bò nào bị nhiễm nữa)
-> …

Sau hai đêm trở lên, trạng thái cuối cùng của những con bò sẽ giống như đầu vào. Có nhiều trạng thái ban đầu và số đêm khác có thể tạo ra trạng thái đầu vào, chẳng hạn như:
0 đêm: 10001
1 đêm: -> 11011
2 đêm: -> 11111

hoặc:
0 đêm: 01001
1 đêm: -> 11111

hoặc:
0 đêm: 01000
1 đêm: -> 11100
2 đêm: -> 11110
3 đêm: -> 11111

Tất cả các trạng thái ban đầu này đều có ít nhất một con bò bị nhiễm bệnh.
ĐẦU VÀO MẪU:
6
011101

ĐẦU RA MẪU:
4

Những gì tôi đã thử:

Tôi đã thử 2 giải pháp khác nhau, vượt qua một số điểm kiểm tra, một số điểm khác nhau:
1.

#include <iostream>
#include <vector>

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected += (current_sequence_length + 1) / 2; // Adjusted logic
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                total_infected += current_sequence_length;
            }
        }
    }

    // Consider the last cow
    total_infected += consecutive_ones;

    // If all cows are infected, set total_infected to 1
    if (total_infected == cow_states.size()) {
        total_infected = 1;
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}

2.

#include <iostream>
#include <vector>

bool is_consecutive_ones(const std::vector<int>& cow_states, int index) {
    return index >= 2 && cow_states[index - 1] == 1 && cow_states[index - 2] == 1;
}

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;
    bool override_total = false;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3 && current_sequence_length % 2 == 1) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected++;
                } else if (is_consecutive_ones(cow_states, i)) {
                    total_infected++;
                    override_total = true;
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                if (current_sequence_length == 3) {
                    if (i - 1 >= 0 && cow_states[i - 1] == 0 && i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                        total_infected++;
                    } else {
                        total_infected += current_sequence_length;
                    }
                } else {
                    total_infected += current_sequence_length;
                }
            }
        }
    }

    if (override_total) {
        total_infected += consecutive_ones;
    } else {
        total_infected += cow_states.back(); // Consider the last cow
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}


This is my basic logic, however I do believe it may be incorrect.

Logic for counting how many cows (n is a constant for a number of 1s):

Middle cases:
If there is a sequence of 1s with only a single 1 (a sequence is a continued string of 1s, separated by 0s from other 1s), count how many 1s there are to find total.
If there is a sequence of 2 1s, count how many 1s there are to find total
If there is a sequence of n 1s, where n is odd and n>=3, use the formula: x=(n+1)/2 to determine the day it is. Then apply the formula n=2x-1 to weed through all sequences of consecutive 1s to determine if the day count is correct.
If it is not correct (a sequence of an even number of consecutive 1s) or (an odd number of 1s not equating to the aforementioned string), count how many 1s there are to find total.
If it is correct and applies to all other sequences, add 1 to the total.

Special cases (on both ends):
If the bitstring starts with 10, erase current total and count how many 1s there are to find correct total.
If the bitstring ends in 01, erase current total and count how many 1s there are to find correct total.
If the bristring starts with 110, there may be 2 original cows, or only 1, depending on the middle sections.
If the bristring ends with 011, there may be 2 original cows, or only 1, depending on the middle sections.
If the bitstring starts with x0 (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.
If the bitstring starts with 0x (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.