Terrível doença COWVID-19 espalha entre vacas mundiais. Farmer John toma toda precaução para proteger rebanho.
Celeiro longo estreito, $N$ baias ($2 \leq N \leq 10^5$) em fila, ocupadas ou vazias. Lendo importância da distância maximiza $D$; $D$ distância das duas ocupadas mais próximas. Se3 e8, $D = 5$.
Duas novas vacas em baias antes vazias para máximo $D$. Não move existentes, só atribui novas.
Entrada
Primeira linha $N$, próxima cadeia01 tamanho $N$,0 vazio1 ocupado. Pelo menos dois0, há espaço.
Saída
Imprima máximo $D$ após colocar duas otimamente, menor distância ocupada.
Exemplos
Entrada 1
14 10001001000010
Saída 1
2
Nota
Pode 10x010010x0010, x novas. $D = 2$, maior $D$ impossível.
Subtarefas
- Testes2–6 satisfazem $N\le 10$.
- Testes7–8 satisfazem $N\le 100$.
- Testes9–11 satisfazem $N \le 5000$.
- Testes12–15 sem limites extras.
Autor do problema: Brian Dean