Terribile malattia COWVID-19 si diffonde fra mucche mondiali. Farmer John prende tutte precauzioni per mandria.
Fienile lungo stretto, $N$ stalli ($2 \leq N \leq 10^5$) in fila, occupati o vuoti. Letta importanza distanza, massimizza $D$; $D$ distanza dei due occupati più vicini. Se3 e8, $D = 5$.
Due nuove mucche in stalli prima vuoti per massimo $D$. Non muove esistenti, solo assegna nuove.
Input
Prima riga $N$, successiva stringa01 lunga $N$,0 vuoto1 occupato. Almeno due0, spazio sufficiente.
Output
Stampa massimo $D$ dopo aggiunta ottima di due, minima distanza occupata.
Esempi
Input 1
14 10001001000010
Output 1
2
Nota
Possibile 10x010010x0010, x nuove. $D = 2$, maggiore $D$ impossibile.
Sottoproblemi
- Test2–6 soddisfano $N\le 10$.
- Test7–8 soddisfano $N\le 100$.
- Test9–11 soddisfano $N \le 5000$.
- Test12–15 senza vincoli extra.
Autore del problema: Brian Dean