Как решить задание?

[Usernameistaken]

Помогите пожалуйста решить задание.
В поселке, где N домов, расположенных вдоль прямой дороги с одной стороны на равных расстояниях, прокладывают телефонную связь. Задать количество телефонных аппаратов в каждом доме. Каждый телефон должен быть соединен с АТС отдельным кабелем. Определить, в каком доме необходимо установить АТС, чтобы суммарная длина кабелей была минимальной.

[digitalis]

Ставишь АТС в средний дом, считаешь длины, имея в виду число аппаратов. Потом на один дом ближе к началу. Если стало меньше, продолжаешь в том же духе, пока не станет больше. Если уже в первой попытке было больше, то считаешь таким же образом в другую сторону. И выходишь на оптимум.
Или тупо в лоб, полным перебором: с первого по последний.
Простейшая задача дискретной оптимизации.

[evg_m]

равные расстояния

дом в котором разница в числе аппаратов слева и справа будет минимальна. ???

[digitalis]

... с одной поправкой: учитывать не только число аппаратов, но и удалённость от АТС.
Вот решение (тупо, в лоб, полным перебором):

procedure TForm1.Button3Click(Sender: TObject);
var i,j,le,ri,mn,imn,sum: integer ; A: array [0..50] of integer ;
st: string ;
begin
   st := '' ;
   for i := 0 to 50 do
      begin
       A[i] := random (20) + 1 ;
       st := st + Format ('%4d',[A[i]])
      end;
   Memo1.Lines.Add(st) ;
   mn := 1000000 ;
   for i := 0 to 50 do
      begin
        le := 0 ;
        for j := 0 to i-1 do le := le + A[j] * Abs(i-j) ;
        ri := 0 ;
        for j := i+1 to 50 do ri := ri + A[j] * Abs(i-j) ;
        sum := le + ri ;
        if sum < mn then
           begin mn := sum ; imn := i end ;
        st := Format('%3d %3d %5d %5d %5d %5d',[i,A[i],le,ri,le-ri,sum]) ;
        Memo1.Lines.Add(st) ;
      end ;
   Memo1.Lines.Add(Format('%4d = %4d',[imn,mn])) ;
end;

......
23 1 3222 3691 -469 6913
24 10 3468 3439 29 6907
25 2 3724 3197 527 6921
......
24 = 6907

[ViktorR]

Что-то уж больно сложно
Если в посёлке n домов на расстоянии dL друг от друга, в каждом доме ki аппаратов и АТС в доме с номером m, то можно записать:

d1 = k1*(m - 1)*dL  {для первого дома}
d2 = k2*(m - 1)*dL  {для второго дома}
...
dn = kn*(m - n)*dL  {для n-ого дома}

Суммируем расстояния.
Для домов, чьи номера меньше m - положительные значения, а для домов с номером больше m - отрицательные. Оптимальной будет сумма равная нулю.
Полагаем dL = 1. Тогда:

(k1 + k2 + ... kn)*m = k1*1 + k2*2 + ... kn*n   {номер дома умножаем на число аппаратов}

Теперь имеем:

m = (k1*1 + k2*2 + ... kn*n) / (k1 + k2 + ... kn)

Остался вопрос: Так как m - целое число, то при делении округлять в меньшую или большую сторону?
В принципе можно тупо проверить только для двух номеров [m] (меньшее целое) или ]m[ (большее целое.

PS: digitalis А вы можете проверить?

[digitalis]

Я так глубоко не вник - ночь, сонливость - но результат, по-моему, всё тот же: полный перебор. Ваш вариант (#3 с моим добавлением) я проверил ( (слева - справа) -> min), оптимум совпадает с моим (#4). Но по-моему, слишком много чести для такой элементарнейшей задачи, чтоб мы её ещё шлифовали до крайности.

[ViktorR]

Ваш вариант я проверил

Спасибо за проверку. Самому пока никак ...