El granjero John tiene N vacas en una línea (1≤N≤3⋅10^5). Desafortunadamente, hay una enfermedad que se está extendiendo por todas partes.
Inicialmente, algunas vacas empiezan infectadas. Cada noche, una vaca infectada transmite la enfermedad a las vacas de izquierda y derecha (si existen). Una vez que una vaca está infectada, permanece infectada.
Después de algunas noches, el granjero John se da cuenta de que el problema se ha salido de control, por lo que examina a sus vacas para determinar quién tiene la enfermedad. Encuentre el número mínimo de vacas que podrían haber comenzado con la enfermedad.
APORTE:
La primera línea contiene N, la cantidad de vacas que tiene el granjero John.
La siguiente línea contiene una cadena de bits de N caracteres de solo 1 y 0, donde un 1 representa una vaca infectada y un 0 representa una vaca no infectada después de un cierto número de noches.
PRODUCCIÓN:
Genera un único número entero: el número mínimo de vacas que podrían haber comenzado con la enfermedad.
ENTRADA DE MUESTRA:
5
11111
SALIDA DE MUESTRA:
1
Supongamos que la vaca del medio fuera la única que empezó infectada. Luego las vacas quedarían infectadas en el siguiente orden:
0 noches: 00100 (la tercera vaca está inicialmente infectada)
1 noche: -> 01110 (la segunda y cuarta vaca ahora están infectadas)
2 noches: -> 11111 (la primera y la quinta vaca ahora están infectadas)
3 noches: -> 11111 (todas las vacas ya estaban infectadas, por lo que no hay vacas adicionales infectadas)
->…
Después de dos o más noches, el estado final de las vacas se parecería al de entrada. Hay muchos otros estados iniciales y número de noches que podrían haber producido el estado de entrada, como por ejemplo:
0 noches: 10001
1 noche: -> 11011
2 noches: -> 11111
o:
0 noches: 01001
1 noche: -> 11111
o:
0 noches: 01000
1 noche: -> 11100
2 noches: -> 11110
3 noches: -> 11111
Todos estos estados iniciales contienen al menos una vaca infectada.
ENTRADA DE MUESTRA:
6
011101
SALIDA DE MUESTRA:
4
Lo que he probado:
Probé 2 soluciones diferentes, pasando algunos puntos de prueba, algunos diferentes:
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; }
Esta es mi lógica básica, sin embargo creo que puede ser incorrecta.
Lógica para contar cuántas vacas (n es una constante para un número de unos):
Casos medios:
Si hay una secuencia de unos con un solo 1 (una secuencia es una cadena continua de unos, separada por ceros de otros unos), cuente cuántos unos hay para encontrar el total.
Si hay una secuencia de 2 unos, cuenta cuántos unos hay para encontrar el total
Si hay una secuencia de n 1, donde n es impar y n>=3, use la fórmula: x=(n+1)/2 para determinar el día que es. Luego aplique la fórmula n=2x-1 para eliminar todas las secuencias de unos consecutivos para determinar si el recuento de días es correcto.
Si no es correcta (una secuencia de un número par de unos consecutivos) o (un número impar de unos que no equivale a la cadena antes mencionada), cuente cuántos unos hay para encontrar el total.
Si es correcto y se aplica a todas las demás secuencias, suma 1 al total.
Casos especiales (en ambos extremos):
Si la cadena de bits comienza con 10, borre el total actual y cuente cuántos unos hay para encontrar el total correcto.
Si la cadena de bits termina en 01, borre el total actual y cuente cuántos unos hay para encontrar el total correcto.
Si el bristring comienza con 110, puede haber 2 vacas originales, o solo 1, dependiendo de las secciones intermedias.
Si el bristring termina en 011, puede haber 2 vacas originales, o solo 1, dependiendo de las secciones intermedias.
Si la cadena de bits comienza con x0 (donde z es una cadena de bits que representa el número x de unos), puede haber x vacas originales o solo 1, dependiendo de las secciones intermedias.
Si la cadena de bits comienza con 0x (donde z es una cadena de bits que representa el número x de unos), puede haber x vacas originales o solo 1, dependiendo de las secciones intermedias.
Solución 1
Deberías utilizar alguna estrategia de “divide y vencerás” para resolver ese problema. Para hacerlo debes escribir diferente funciones para cada criterio.
Lo mejor es pensar en alguna estructura de datos, como una serie de vacas, para los datos en los que funcionan sus funciones.
Luego escriba pruebas para cada función y elimine los errores. Escriba algún resultado útil, como alguna impresión del estado de todas las vacas como textos formateados.
Entonces puedes terminar con algunos
infect(Cows *cows, Cows *resulting, int pos)
función que busca si pos está infectado y luego infecta el área anterior y posterior en el área resultante. De lo contrario, podrías infectarte demasiado. Puede agregar algún valor de días_infectados para depurarlo mejor.
Buena suerte con tu tarea. Úselo para mejorar sus habilidades de codificación, como la depuración.
コメント