Training - Mercato del pesce

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

Scarica la traccia in C++: consegne.cpp

Scarica la traccia in C#: consegne.cs

Scarica la traccia in Go: consegne.go

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

Scarica la traccia in Java: consegne.java

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

Scarica la traccia in Pascal: consegne.pas

Scarica la traccia in Python: consegne.py

Scarica la traccia in VisualBasic: consegne.vb

Descrizione del problema

Il famoso mercato ittico di Livorno viene rifornito continuamente per assicurarsi che ci sia sempre pesce fresco.

Per oggi è programmato l'arrivo di $N$ casse di pesce che dovranno essere trasportate dal porto al mercato.

"Pesce"

Il furgone frigorifero che trasporta il pesce può portare un qualunque numero di casse, impiega un minuto a compiere il tragitto dal porto al mercato e un altro minuto per tornare al porto: impiega quindi un totale di due minuti per ogni consegna. In particolare, se la consegna parte al minuto $i$ , il furgone non sarà al porto al minuto $i + 1$ e tornerà disponibile al minuto $i + 2$ .

Ogni minuto, per $N$ minuti numerati da $0$ a $N - 1$ , arriva al porto una cassa di pesce. Se il furgone è al porto, la cassa viene caricata subito sul furgone, altrimenti sarà caricata al minuto successivo e viene pagata una penale di $P_i$ euro per essere stata lasciata al caldo.

Inoltre, per ogni cassa, viene pagata una tassa di stazionamento di $t$ euro, dove $t$ è il tempo che passa da quando il pesce arriva al porto a quando il furgone su cui si trova parte per il mercato ittico.

Il tuo compito è scegliere in quali minuti far partire il furgone in modo da minimizzare il costo totale per portare le $N$ casse di pesce dal porto al mercato ittico. Quanto puoi spendere al minimo?

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 $P_{0}, \, \ldots, \, P_{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 a 64 bit $\mathtt{ris}$ .

Assunzioni

$T = 20$ , nei file di input che scaricherai saranno presenti esattamente $20$ casi di test.
$1 \leq N \leq 10^6$ .
$0 \leq P_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 N \leq 20 & 1, 2 \\ \hline N \leq 3000 & 3, 4, 5 \\ \hline P_i \leq 10 \text{ per ogni } 0 \leq i < N & 6, 7 \\ \hline \text {Nessuna assunzione aggiuntiva} & 8, 9, 10 \\ \hline \end{array}$

Esempi di input/output

Input:

4

4
1 3 5 4

5
1 2 1 4 1

6
5 1 4 6 2 3

7
10 2 1 10 3 4 5

Output:

Case #1: 6
Case #2: 5
Case #3: 7
Case #4: 9

Spiegazione

Nel primo caso di esempio è possibile pagare $6$ euro facendo partire il furgone al minuto $3$ , cioè quando arriva l'ultima cassa.

In questo modo tutte le casse vengono caricate subito e non servirà pagare alcuna penale. La tassa per l'attesa è, in ordine, di $3$ , $2$ , $1$ e $0$ euro, dunque $6$ in totale.

Nel secondo caso di esempio, se il furgone parte ai minuti $1$ e $4$ , sarà necessario pagare una penale di $P_2 = 1$ euro perché al minuto $2$ il furgone si troverà al mercato. I tempi d'attesa sono rispettivamente $1$ , $0$ , $2$ , $1$ e $0$ , la cui somma è $4$ .

Il costo totale è dunque di $5$ euro.

In entrambi i casi non è possibile fare di meglio.