Collezionismo di robot

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: collezionismo.c
• Scarica la traccia in C++: collezionismo.cpp
• Scarica la traccia in Python: collezionismo.py
• Scarica la traccia in Java: collezionismo.java
• Scarica la traccia in C#: collezionismo.cs
• Scarica la traccia in JavaScript: collezionismo.html
• Scarica la traccia in JavaScript (Node.js): collezionismo.js

Descrizione del problema

Luigi è un collezionista di modellini di robot. Finalmente si è deciso a sistemare la sua collezione in una serie di bacheche, ma ha bisogno del tuo aiuto per disporla ottimalmente!

Luigi possiede in totale $N$ modellini, ognuno dei quali ha un valore di collezionismo $C_i$, che vuole disporre su $K$ scaffali. Ogni modellino deve essere messo su esattamente uno scaffale e ogni scaffale deve contenere almeno un modellino.

Poiché Luigi non vuole far sfigurare nessun modellino della sua preziosa collezione, vuole assicurarsi che la differenza dei valori di collezionismo $C_i$ dei modellini su uno stesso scaffale non sia troppo alta. Luigi quindi assegna ad ogni scaffale un fattore di discrepanza $D_j$, definito come la differenza tra il massimo ed il minimo valore di collezionismo dei modellini su quello scaffale.

Luigi, per riuscire nel suo intento, vuole quindi cercare di minimizzare i fattori di discrepanza $D_j$ dei $K$ scaffali. Qual è il valore minimo della somma di questi fattori?

Dati 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 da $2$ righe:

• la prima riga contiene i due interi $N$ e $K$;
• la seconda riga contiene $N$ interi, i valori di collezionismo $C_i$.

Dati 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 #t: s

dove t è il numero del caso di test (a partire da $1$) e il valore s è la somma minima dei fattori di discrepanza dei $K$ scaffali.

Assunzioni

• $T = 15$, nei file di input che scaricherai saranno presenti esattamente $15$ casi di test.
• $1 \le K \le N \le 10000$.
• $0 \le C_i \le 10^9$ per ogni $0 \le i < N$.

Nei primi $6$ casi di test valgono le seguenti assunzioni aggiuntive:

• $N \le 50$.
• $K \le 6$.

Esempi di input/output

---

Input:

2

4 2
7 9 3 1

6 3
4 42 23 0 21 2

---

Output:

Case #1: 4
Case #2: 6

---

Spiegazione

Nel primo caso d'esempio Luigi può mettere il primo ed il secondo modellino nel primo scaffale, ottenendo un fattore di discrepanza $2$, e il terzo e quarto modellino nel secondo scaffale, ottenendo di nuovo $2$. La somma minima è quindi $4$.

Nel secondo caso d'esempio Luigi può mettere il secondo modellino da solo nel primo scaffale, ottenendo $0$, il primo, quarto e sesto modellino nel secondo scaffale, ottenendo $4$, e il terzo e quinto modellino nel terzo scaffale, ottenendo $2$. La somma minima è quindi $6$.