Campo da soldatini

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: soldatini.c
• Scarica la traccia in C++: soldatini.cpp
• Scarica la traccia in Python: soldatini.py
• Scarica la traccia in Java: soldatini.java
• Scarica la traccia in C#: soldatini.cs
• Scarica la traccia in JavaScript: soldatini.html

Descrizione del problema

Il nuovo gioco di Giorgio presenta $2$ tipi di pedine, i soldatini e i muri.

Inizialmente sono presenti $N$ pedine disposte lungo una riga, identificate da una stringa $S$ di lunghezza $N$, dove $S_i$ è $1$ se la pedina $i$ è di tipo soldatino e $0$ se è di tipo muro per $0 \le i \le N-1$. Dario sta provando il gioco e ha notato che avere un grande gruppo di soldatini è molto utile per vincere una partita, dove un gruppo di soldatini è un insieme di pedine consecutive di tipo soldatino. Per garantirsi la vittoria Dario può sostituire una pedina di tipo muro con una pedina di tipo soldatino. Questa operazione può essere eseguita una sola volta, altrimenti rischierebbe di essere scoperto. Aiuta Dario a calcolare qual è la dimensione massima di un gruppo di soldatini che può ottenere.

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• la prima riga contiene l'intero $N$.
• la seconda riga contiene la stringa $S$.

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è dimensione massima di un gruppo di soldatini che Dario può ottenere.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $2 \le N \le 300000$
• La stringa $S$ ha lunghezza $N$ e contiene solo caratteri $0$ e $1$.

Nei primi $5$ casi di test vale $N \le 8000$.

Esempi di input/output

Input:

2

5
11001

7
0110111

Output:

Case #1: 3
Case #2: 6

Spiegazione

Nel primo caso d'esempio, può sostituire il muro in posizione $2$ con un soldatino, ottenendo un gruppo di 3 soldatini e un gruppo di 1 soldatino. La dimensione massima di un gruppo di soldatini è quindi $3$.

Nel secondo caso d'esempio, può sostituire il muro in posizione $3$ con un soldatino, ottenendo un unico gruppo di 6 soldatini.