#2537
Benzinarii1
În Piatra Neamț sunt N+2
locații numerotate de la 0
la N+1
, de la stânga la dreapta. Distanța dintre două locații i
si j
este egală cu |i – j|
. La început, în locațiile 0
și N+1
, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N
benzinării, una în fața fiecărei case.
Înainte să construiască o benzinărie, constructorii calculează valoarea S
egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T
. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S
recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S
va deveni 0
și suma totală T
nu se va mai schimba.
Calculați T
pentru o valoare dată N
.
Olimpiada internațională pe Echipe, 2018