Pruebas en lotes
En el año 2020 el virus SARS-CoV-19 se expandió por todo el mundo provocando una pandemia global por la enfermedad COVID-19. Sin vacuna, sin la población inmunizada, el virus se extendió como la pólvora poniendo en peligro la salud de miles de millones de personas.
Para frenar la extensión de la enfermedad multitud de países limitaron la movilidad de la población que se recluyeron en sus casas para evitar contagiar o ser contagiados. Los comercios cerraron, las fábricas se pararon y los museos dejaron de recibir visitas.
Pero la limitación de movimientos era sólo una parte de la solución. Cuando el índice de incidencia bajó lo suficiente y se comenzó a retomar la actividad, el objetivo fue identificar personas contagiadas por el virus pero que, al ser asintomáticos, no eran conscientes de que podían contagiar a otros. Debido a eso se hicieron miles de costosos tests que sobrecargaron a los laboratorios.
Para evitar esa sobrecarga se pusieron en marcha lo que se conoció como test por lotes: en lugar analizar una muestra individual, se analizaban muestras de varias personas. Si todos ellos eran negativos, se ahorraban muchos tests. Si alguno era positivo, tocaba analizar muestras agregadas de menos gente. Como es lógico, la técnica ahorra tests sólo cuando la probabilidad de positivos es muy baja (hay estudios que dicen que la tasa tiene que estar por debajo de 0.01).
Para conocer el ahorro exacto de test se hicieron muchas simulaciones que asumían una capacidad de detección perfecta y que la interacción de distintas muestras entre sí no alteraba los resultados. En concreto, se estudió cuántos test había que hacer si se seguía el siguiente procedimiento:
- Si solo hay una muestra, se hace el test y se tiene el resultado.
- Si hay más de una muestra, se juntan todas y se hace un único test.
- Si la prueba da negativa, todos son negativos.
- Si la prueba da positiva, se divide la muestra en dos mitades (si el número de muestras es impar, la primera mitad será la más grande).
- Se repite el proceso para ambas mitades.
Entrada
La entrada esta compuesta por distintos casos de prueba o simulaciones, cada una ocupando dos líneas. La primera línea contiene el número n de muestras (1 ≤ n ≤ 100.000). La segunda línea contiene una cadena con n caracteres. Un 1 indica una muestra positiva y un 0 una muestra negativa.
La entrada termina con una línea con un 0 que no debe procesarse.
Salida
Por cada caso de prueba se escribirá una única línea con el número de pruebas necesarias para conocer el resultado de todas las muestras si se sigue el procedimiento de análisis de pruebas por lotes descrito.
Entrada de ejemplo
8 00000000 8 00000001 7 0000001 7 1000000 0
Salida de ejemplo
1 7 5 7