wind

Intuiție / reformulare

„Orașe egale, din centrale vecine, fiecare centrală folosită” se traduce simplu: împart șirul de $N$ centrale în $k$ bucăți consecutive de lungime egală $g = N / k$. Ca să iasă bucăți egale, $k$ trebuie să dividă $N$. Și se cer cel puțin $2$ orașe.

• C1 numără pur și simplu câte valori valide de $k$ există: divizorii lui $N$ cu $k \ge 2$.
• C2 caută gruparea „cea mai echilibrată”: pentru fiecare $k$, energiile orașelor sunt sumele bucăților, iar dezechilibrul $P(k)$ este energia maximă minus cea minimă. Vreau $P$ minim; la egalitate de $P$, vreau cât mai multe orașe.

Ideea cheie