In base all'hint precedente il problema puo' essere visto come il problema di trovare un matching di cardinalita' k e peso minimo entro il grafo completo di 3k nodi (ognuno corrispondente ad uno dei numeri in input) e dove il peso di un arco e' dato dalla distanza tra i valori numerici degli elementi rappresentati dagli estremi dell'arco.
Quindi il problema puo' sicuramente essere risolto in tempo polinomiale.
Ora, nel tempo a disposizione, non possiamo scrivere un algoritmo per il matching di peso minimo,
ma questa osservazione ci puo' incoraggiare nella ricerca di un algoritmo ottimo.
Dobbiamo sfruttare la struttura specifica di questo problema di matching.
La struttura specifica non sta tanto nel fatto che il grafo e' completo ma nella pesatura degli archi:
il peso di ogni arco dipende dal solo valore dei due estremi.
Se tutti i numeri in input li collochiamo su una retta, come si dispongono gli archi del matching ottimo?
Possono overlapparsi (ossia condividere segmenti della retta)?
Riesci a vedere altra struttura utile?