Il fienile circolare, riconsiderato#10587
La stalla è costituita da un anello di stanze, numerate in senso orario da a lungo il perimetro della stalla. Ogni stanza ha porte che la collegano alle due stanze adiacenti, così come una porta che conduce all'esterno della stalla.
L'agricoltore John vuole che nella stanza si trovino esattamente r_i vacche. Per far entrare le vacche nella stalla in modo organizzato, egli intende aprire porte esterne, permettendo alle vacche di entrare solo attraverso queste porte. Dopo essere entrata, ogni vacca si muove in senso orario attraverso le stanze finché non raggiunge una destinazione adeguata. L'agricoltore John vuole scegliere le porte esterne in modo tale che, dopo essere entrate nella stalla, le vacche percorrano complessivamente la distanza totale minima possibile. Inizialmente le vacche possono disporsi in qualsiasi ordine all'esterno delle porte aperte, e questo non viene considerato nella distanza totale percorsa. Determinate la distanza totale minima che le vacche devono percorrere, se l'agricoltore John scegliesse le porte ottimali da aprire.
La prima riga contiene due numeri interi n~(3 \le n \le 100) e k~(1 \le k \le 7). Nelle successive righe è contenuto un numero intero r_i~(1 \le r_i \le 10^6), dove r_i — è il numero di vacche che devono trovarsi nella stanza .
Stampate la distanza totale minima che le vacche devono percorrere.
L'agricoltore John può aprire le porte e . vacche entrano attraverso la porta e percorrono una distanza totale di per raggiungere le stanze e . vacche entrano attraverso la porta e percorrono una distanza totale di per raggiungere le stanze e .
Esempio 1