Spegni le lampadine

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: spegnitutto.c
• Scarica la traccia in C++: spegnitutto.cpp
• Scarica la traccia in C#: spegnitutto.cs
• Scarica la traccia in Go: spegnitutto.go
• Scarica la traccia in JavaScript: spegnitutto.html
• Scarica la traccia in Java: spegnitutto.java
• Scarica la traccia in Pascal: spegnitutto.pas
• Scarica la traccia in Python: spegnitutto.py
• Scarica la traccia in VisualBasic: spegnitutto.vb

Descrizione del problema

Luca ha superato la paura del buio, e deve spegnere tutte le $N$ lampadine, numerate da $1$ a $N$, nel lungo corridoio della sua casa prima di andare a dormire! Nel corridoio sono presenti $N-1$ interruttori numerati da $1$ a $N-1$. Il loro funzionamento è un po' particolare! Le lampadine $i$ e $i+1$ sono collegate all'$i$-esimo interruttore. Premendo un interruttore entrambe le lampadine ad esso collegate cambieranno di stato: una lampadina cambiando di stato si accende se spenta e si spegne se accesa.

Questo rende un po' complicato spegnere tutto, quindi Luca ha deciso di non andare troppo per il sottile, e se serve svitare direttamente alcune lampadine. Luca può quindi fare le seguenti azioni:

• svita lampadina i: svitare l'$i$-esima lampadina, spegnendola. Una volta svitata, la lampadina non potrà più essere accesa né riavvitata.
• premi l'interruttore i: premere l'interruttore $i$-esimo, cambiando lo stato delle lampadine $i$ e $i+1$ (se e solo se non sono svitate).

Luca è molto stanco e vorrebbe finire al più presto il suo lavoro: trova il minimo numero di azioni necessarie per portare il buio nel corridoio! Conta come una azione sia svitare una lampadina che premere un interruttore.

Formato 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:

• una riga contenente l'intero $N$, il numero di lampadine nel corridoio.
• una riga contenente gli $N$ interi $A_{1}, \, \ldots, \, A_{N}$, lo stato delle lampadine: $A_i = 1$ indica che la lampadina $i$ è accesa e $A_i = 0$ che è spenta.

Formato 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 #test: ", dove test è il numero del caso di test (a partire da $1$), seguita dall'intero $\mathtt{ris}$.

Assunzioni

• $T = 20$, nei file di input che scaricherai saranno presenti esattamente $20$ casi di test.
• $1 \leq N \leq 10^5$.
• $0 \leq A_i \leq 1$.

Gruppi di testcase

I casi di test sono divisi in gruppi. Ogni gruppo vale $5$ punti, e per ottenere il punteggio relativo ad esso è necessario risolvere correttamente tutti i casi di test che lo compongono.

Su alcuni gruppi valgono delle assunzioni aggiuntive:

$\small \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \texttt{Assunzioni} & \texttt{Gruppi} \\ \hline \text{Inizialmente tutte le lampadine sono accese} & 1, 2 \\ \hline \text{Non ci sono due lampadine accese vicine} & 3, 4 \\ \hline N \leq 20 & 5, 6 \\ \hline \text {Nessuna assunzione aggiuntiva} & 7, 8, 9, 10 \\ \hline \end{array}$

Esempi di input/output

---

Input:

4

4
1 1 0 1

5
1 0 1 0 1

6
1 1 1 1 1 0

7
0 1 1 1 0 1 0

---

Output:

Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 3

---

Spiegazione

Nel primo caso di esempio, le lampadine nel corridoio sono nello stato $A = [1, 1, 0, 1]$, come in figura:

per spegnere le lampadine Luca potrebbe:

1. Premere l'interruttore $1$ cambiando lo stato delle lampadine $1$ e $2$, ottenendo $[0, 0, 0, 1]$.
2. Svitare la lampadina $4$, ottenendo $[0, 0, 0, 0]$.

Quindi, Luca farebbe due azioni e non è possibile farne meno.

Nel secondo caso di esempio, le lampadine nel corridoio sono nello stato $A = [1, 0, 1, 0, 1]$, come in figura:

Per spegnere le lampadine Luca potrebbe:

1. Svitare la lampadina $1$, ottenendo $[0, 0, 1, 0, 1]$.
2. Svitare la lampadina $3$, ottenendo $[0, 0, 0, 0, 1]$.
3. Svitare la lampadina $5$, ottenendo $[0, 0, 0, 0, 0]$.

Tre azioni sono quindi sufficienti e Luca non potrebbe farne di meno.