Fienile circolare (Oro)

Da appassionato di architettura moderna, il Fermer John ha costruito un nuovo fienile a forma di cerchio perfetto. All'interno, il fienile è composto da un anello di $n$ stanze, numerate in senso orario da $1$ a $n$ lungo il perimetro del fienile. Ogni stanza ha porte che la collegano alle due stanze adiacenti, oltre a una porta che conduce all'esterno del fienile.

Il Fermer John possiede $n$ mucche e vuole che in ogni stanza del fienile si trovi esattamente una mucca. Tuttavia, le mucche, essendo un po' disorientate, si sono messe in fila davanti a porte scelte a caso, e più mucche possono trovarsi davanti alla stessa porta. Esattamente c_i mucche si sono messe in fila davanti alla porta della stanza $i$, quindi \sum c_i = n.

Per organizzare il processo di ingresso delle mucche in modo che in ogni stanza finisca esattamente una mucca, il Fermer John utilizza il seguente approccio: ogni mucca entra dalla porta presso cui inizialmente si era messa in fila, e poi si muove in senso orario attraverso le stanze finché non raggiunge la propria destinazione. Se una mucca attraversa $d$ porte, essa consuma d^2 unità di energia. Determinate la quantità minima totale di energia necessaria per distribuire le mucche in modo che in ogni stanza si trovi esattamente una mucca.