Farmer John has N cows in a line (1≤N≤3⋅10^5). Unfortunately, there is a sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads the sickness to the cows on their left and right (if they exist). Once a cow is infected, she stays infected.
After some amount of nights, Farmer John realizes that the issue has gotten out of control, so he tests his cows to determine who has the sickness. Find the minimum number of cows that could have started with the sickness.
INPUT:
The first line contains N, the number of cows that Farmer John has.
The next line contains an N character bitstring of only 1s and 0s where a 1 represents an infected cow and a 0 represents an uninfected cow after some number of nights.
OUTPUT:
Output a single integer: the minimum number of cows that could have started with the sickness.
SAMPLE INPUT:
5
11111
SAMPLE OUTPUT:
1
Suppose the middle cow was the only cow to start off infected. Then the cows would be infected in the following order:
0 nights: 00100 (the third cow is initially infected)
1 night: -> 01110 (the second and fourth cows are now infected)
2 nights: -> 11111 (the first and fifth cows are now infected)
3 nights: -> 11111 (all cows already were infected, so no additional cows are infected)
-> ...
After two or more nights, the final state of the cows would look like the input. There are many other initial states and number of nights that could have produced the input state, such as:
0 nights: 10001
1 night: -> 11011
2 nights: -> 11111
or:
0 nights: 01001
1 night: -> 11111
or:
0 nights: 01000
1 night: -> 11100
2 nights: -> 11110
3 nights: -> 11111
All of these initial states contain at least one infected cow.
SAMPLE INPUT:
6
011101
SAMPLE OUTPUT:
4
What I have tried:
I have tried 2 different solutions, passing a few test points, some different:
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; } else {
total_infected += current_sequence_length;
}
} else {
total_infected += current_sequence_length;
}
}
}
total_infected += consecutive_ones;
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(); }
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.