Logo OII
Accedi / Registrati

Batti gli avversari

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.

Descrizione del problema

Elio Muschio ha deciso di iniziare a giocare a FarmCraft. Il gioco sembra piuttosto divertente, ma c'è un piccolo problema:
Elio è ancora ultimo nella classifica globale, con zero punti. Allenarsi per migliorare sarebbe un'opzione... ma Elio ha in mente un piano decisamente più furbo!

La classifica di FarmCraft è composta da NN giocatori, ordinati dal punteggio più alto al più basso. Ogni giocatore in posizione ii-esima ha un punteggio pari a PiP_i.
In caso di parità di punteggio, viene prima in classifica chi ha raggiunto quel punteggio per primo, quindi ogni posizione nella classifica è distinta.

"img"

Nel negozio del gioco sono disponibili NN box speciali, numerate da 11 a NN, ognuna con un costo di CiC_i monete. Acquistando la box ii-esima, Elio potrà ridurre di 1 punto il punteggio del giocatore che in quel momento occupa la ii-esima posizione nella classifica. Ogni box può essere acquistata un numero qualsiasi di volte. La classifica viene aggiornata dopo ogni cambio di punteggio, in base ai nuovi punteggi dei giocatori.

Dato che Elio Muschio non sa perdere, il suo piano consiste nell'utilizzare queste box per abbassare il punteggio di tutti gli altri giocatori a zero, così che tutti avranno il suo stesso punteggio.

Il tuo compito è aiutare Elio a raggiungere il suo obiettivo spendendo il minimo numero di monete possibile.

Formato di input

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

Ogni caso di test è composto come segue:

  • una riga contenente l'intero NN, il numero di giocatori in classifica.
  • una riga contenente gli NN interi P1, …, PNP_{1}, \, \ldots, \, P_{N}, i punteggi dei giocatori in classifica, dal primo all'ultimo.
  • una riga contenente gli NN interi C1, …, CNC_{1}, \, \ldots, \, C_{N}, il costo delle box.

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 11), seguita dall'intero ris\mathtt{ris}.

Assunzioni

  • T=20T = 20, nei file di input che scaricherai saranno presenti esattamente 2020 casi di test.
  • 1≤N≤1051 \leq N \leq 10^5.
  • 0≤Pi≤1050 \leq P_i \leq 10^5.
  • 0≤Ci≤1050 \leq C_i \leq 10^5.

Gruppi di testcase

I casi di test sono divisi in gruppi.
Ogni gruppo vale 55 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:

AssunzioniGruppiC eˋ ordinato in modo crescente1,2,3C eˋ ordinato in modo decrescente4,5Ci∈{0,1} per ogni i6,7N≤10008∑Pi≤1000009Nessuna assunzione aggiuntiva10\small \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \texttt{Assunzioni} & \texttt{Gruppi} \\ \hline C \text{ è ordinato in modo crescente} & 1, 2, 3 \\ \hline C \text{ è ordinato in modo decrescente} & 4, 5 \\ \hline C_i \in \{0, 1\} \ \text{per ogni } i & 6, 7 \\ \hline N \leq 1000 & 8 \\ \hline \sum P_i \leq 100000 & 9 \\ \hline \text{Nessuna assunzione aggiuntiva} & 10 \\ \hline \end{array}

Esempi di input/output

Input:

2

3
3 1 1 
4 5 2 

5
4 3 2 1 1
2 2 2 2 2

Output:

Case #1: 18
Case #2: 22

Spiegazione

Nel primo caso di esempio, ci sono 33 giocatori con punteggi iniziali [3,1,1][3, 1, 1] e i costi delle box sono [4,5,2][4, 5, 2].

Ricorda che la classifica viene aggiornata dopo ogni acquisto. Elio deve ridurre tutti i punteggi a zero, scegliendo ogni volta una sola box. Ecco una possibile sequenza ottimale:

  1. Elio usa la box 1 al costo di 4 monete, il giocatore in posizione 11 perde un punto e rimane in posizione 11 con 22 punti: la classifica diventa [2,1,1][2, 1, 1]
  2. Elio usa la box 1 al costo di 4 monete: il giocatore in posizione 11 perde un punto e scende in posizione 33 con 11 punti: la classifica diventa [1,1,1][1, 1, 1]
  3. Elio usa la box 3 al costo di 2 monete: il giocatore in posizione 33 perde un punto e rimane in posizione 33 con 00 punti: la classifica diventa [1,1,0][1, 1, 0]
  4. Elio usa la box 1 al costo di 4 monete: il giocatore in posizione 11 perde un punto e scende in posizione 33 con 00 punti: la classifica diventa [1,0,0][1, 0, 0]
  5. Elio usa la box 1 al costo di 4 monete: il giocatore in posizione 11 perde un punto e scende in posizione 33 con 00 punti: la classifica diventa [0,0,0][0, 0, 0]

Elio avrà dunque usato 66 volte la box 11 e 11 volta la box 33 spendendo in totale 1818 monete, non avrebbe potuto fare di meglio.

Nel secondo caso di esempio, Elio può usare 1111 volte la box 11 pagando 2222 monete.