Training - Viaggi in Taxi

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: taxi.c

Scarica la traccia in C++: taxi.cpp

Scarica la traccia in C#: taxi.cs

Scarica la traccia in Go: taxi.go

Scarica la traccia in JavaScript (HTML): taxi.html

Scarica la traccia in Java: taxi.java

Scarica la traccia in JavaScript (wasm-ide): taxi.js

Scarica la traccia in Pascal: taxi.pas

Scarica la traccia in Python: taxi.py

Scarica la traccia in VisualBasic: taxi.vb

Descrizione del problema

Il museo sulla storia delle Olimpiadi di Informatica ha appena concluso la sua inaugurazione riscuotendo un discreto successo. Ora gli $N$ visitatori sono in attesa di prendere un taxi per tornare a casa e fuori dal museo si è creata una lunga coda.

"Coda"

In coda alla fermata del taxi, gli $N$ visitatori sono divisi in comitive. Ciascuna comitiva è identificata da un proprio numero; i numeri identificativi dei gruppi sono numeri qualsiasi, non in qualche ordine particolare.

In particolare la persona $i$ appartiene al gruppo $G_i$ e i gruppi si sono messi in fila in modo che le persone dello stesso gruppo siano tutte di seguito.

Siccome ogni comitiva vuole viaggiare su un solo taxi per non dividersi e non vuole condividere il taxi con altre comitive, quanti taxi servono per accompagnare a casa tutti i visitatori?

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$ .
una riga contenente gli $N$ interi $G_{0}, \, \ldots, \, G_{N-1}$ .

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^4$ .
$0 \leq G_i \leq 10^4$ .

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{ Ogni } G_i \text{ ha lo stesso valore} & 1 \\ \hline G_i \text{ assume al massimo } 2 \text{ valori distinti} & 2 \\ \hline G_i = G_{i-1} \text{ o } G_i = G_{i-1} + 1 \text{ per ogni } i = 1 \ldots N - 1 & 3 \\ \hline \text{Nessuna assunzione aggiuntiva} & 4, 5, 6, 7, 8, 9, 10 \\ \hline \end{array}$

Esempi di input/output

Input:

2

3
2 2 1

7
2 2 3 3 3 4 4

Output:

Case #1: 2
Case #2: 3

Spiegazione

Nel primo caso di esempio, ci sono due persone del gruppo $2$ e una persona del gruppo $1$ . Quindi, abbiamo bisogno di due taxi.

Nel secondo caso di esempio, ci sono due persone del gruppo $2$ , tre persone del gruppo $3$ e due persone del gruppo $4$ . Quindi, abbiamo bisogno di tre taxi.