Training - Investimenti su sequenza di titoli

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

Scarica la traccia in C++: investitutto.cpp

Scarica la traccia in C#: investitutto.cs

Scarica la traccia in Go: investitutto.go

Scarica la traccia in JavaScript: investitutto.html

Scarica la traccia in Java: investitutto.java

Scarica la traccia in Pascal: investitutto.pas

Scarica la traccia in Python: investitutto.py

Scarica la traccia in VisualBasic: investitutto.vb

Descrizione del problema

Per il suo compleanno, a Elia hanno regalato un titolo di investimento della Eliot. Il titolo oggi ha un valore $V_0$ monete, ma il suo valore sale di $G_0$ monete ogni giorno, per cui tra $k$ giorni varrà $V_0 + k \cdot G_0$ . Il nostro amico allora ha deciso di darsi alla finanza!

Tuttavia, un solo intermediario accetta di fare affari con Elia e con delle condizioni molto restrittive. Ogni giorno, l'intermediario offre a Elia un singolo titolo: nel giorno $i$ , il valore iniziale del titolo offerto è $V_i$ e aumenterà di $G_i$ ogni giorno successivo. Se il valore del titolo che Elia possiede il giorno $i$ vale almeno quanto quello offerto dall'intermediario, Elia può decidere di scambiare il titolo che ha con quello offerto, ma senza ricevere nessun resto in cambio.

Quello che però l'intermediario non sa è che Elia ha degli informatori, ed è riuscito a scoprire quali titoli offrirà l'intermediario nei prossimi $N-1$ giorni. Sa quindi per ogni giorno $i$ il valore $V_i$ e il guadagno $G_i$ del titolo che verrà proposto. $V_0$ e $G_0$ sono il valore iniziale e il guadagno giornaliero del titolo che viene regalato ad Elia.

"img"

Il giorno $N$ Elia vende il titolo in suo possesso. Sapresti dire quanto Elia può guadagnare al massimo, scegliendo al meglio ogni giorno se scambiare o meno il suo titolo con quello proposto dall'intermediario?

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 $V_{0}, \, \ldots, \, V_{N-1}$ .
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 V_i \leq 10^6$ .
$0 \leq G_i \leq 100$ .

Gruppi di testcase

I casi di test sono suddivisi in 10 gruppi.
Ogni gruppo vale 5 punti, ottenuti solo se tutti i testcase del gruppo vengono risolti correttamente.
Gruppi diversi possono contenere testcase rispondenti alle stesse assunzioni.

$\small \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \texttt{Assunzioni} & \texttt{Gruppi} \\ \hline V_i = \text{costante per ogni i} & 1,2 \\ \hline G_i \text{ assume al più due valori distinti} & 3,4 \\ \hline N \leq 10 & 5,6 \\ \hline N \leq 1000 & 7,8 \\ \hline \text{Nessuna assunzione aggiuntiva} & 9,10 \\ \hline \end{array}$

Esempi di input/output

Input:

Output:

Case #1: 17
Case #2: 18

Spiegazione

Nel primo caso di esempio, L'azione di Elia il giorno $0$ vale $4$ e il suo valore arriverà a $8$ il giorno $1$ .

"img"

Elia può dunque:

scambiare il titolo in suo possesso il giorno $1$ per un'azione del titolo $V_1$ dal valore di $7$ . Il giorno $2$ l'azione arriverà al valore di $7+5=12$ .
tenere il titolo in suo possesso il giorno $2$ . Il giorno $3$ l'azione arriverà al valore di $7+5*2=17$ . Elia venderà dunque la sua azione guadagnando $17$ monete.

Nel secondo caso di esempio, Elia dovrà procedere come nel caso precedente fino il giorno $2$ , quando gli converrà scambiare l'azione in suo possesso per un'azione del titolo $V_2$ che il giorno $3$ varrà $11+7=18$ .