Stalla circolare (Bronzo)#10581
Essendo un ammiratore dell'architettura moderna, il Fermer Giovanni ha costruito una nuova stalla a forma di cerchio perfetto. All'interno, la stalla è composta 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, oltre a una porta che conduce all'esterno della stalla.
Il Fermer Giovanni vuole che in ogni stanza finiscano esattamente r_i mucche. Per far entrare le mucche nella stalla in modo organizzato, egli progetta di aprire la porta esterna di esattamente una stanza, attraverso la quale le mucche potranno entrare. Successivamente, ogni mucca si muove in senso orario attraverso le stanze finché non raggiunge la propria destinazione. Il Fermer Giovanni vuole scegliere la porta esterna in modo da minimizzare la distanza totale percorsa da tutte le mucche. Determinate la distanza totale minima che le mucche devono percorrere, se egli sceglie la porta ottimale. La distanza percorsa da una singola mucca è definita come il numero di porte interne attraverso cui essa passa.
La prima riga contiene un numero intero n~(3 \le n \le 1000). Le successive righe contengono ciascuna un numero intero r_i~(1 \le r_i \le 100).
Stampate la distanza totale minima che tutte le mucche devono percorrere.
In questo esempio, la soluzione ottimale consiste nel far entrare le mucche attraverso la porta esterna della stanza in cui devono essere collocate mucche.
Esempio 1