Помогите пожалуйста решить задачу о деревянной рейке и связанных гвоздях

[Klavdia]

В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются верёвочками так, чтобы выполнялись следующие условия:
к каждому гвоздю была привязана хотя бы одна верёвочка;
суммарная длина верёвочек была бы минимальной. Написать программу, которая связывает пары гвоздей верёвочками как описано выше.
Технические требования: Входными данными являются число гвоздей и их координаты, выходными минимальная суммарная длина и пары соединений гвоздей.
Замечание. Задача решается без перебора.

[Serge_Bliznykov]

вот в этой теме есть решение от BDA на C++
перепишите его на Паскаль и получите нужный код.

[BDA]

Serge_Bliznykov, вот чувствовал, что уже видел эту задачку, а найти не смог
А что решение писал, вообще вылетело из головы

[Poma][a]

А задачка-то известная.. и на acmp есть..

type
        TArr = array [1..100] of Integer;
 
function Min (a, b : Integer) : Integer;
 
begin
        if a < b then
                Min := a
        else
                Min := b
end;
 
procedure Swap (var a, b : Integer);
 
var
        t : Integer;
 
begin
    t := a;
    a := b;
    b := t;
end;
 
procedure SortArr (var a : TArr; const n : Integer);
 
var
        i, j : Integer;
        min : Integer;
 
begin
    for i := 1 to n-1 do begin
        min := i;
        for j := i+1 to n do
            if a[j] < a[min] then
                min := j;
        Swap (a[i], a[min]);
    end;
end;
 
 
var
        a, b : TArr;
        j, n, i, t1, t2, t : Integer;
 
begin
        Assign (input, 'input.txt');
        Reset (input);
 
        Assign (output, 'output.txt');
        Rewrite (output);
        ReadLn (n);
 
        for i := 1 to n do
                Read (a[i]);
 
 
        SortArr (a, n);
 
 
 
        for i := 2 to n do
                b[i-1] := a[i] - a[i-1];
 
 
        b[2] := b[1] + b[2];
 
        for i := 3 to n-1 do
                b[i] := Min (b[i-1], b[i-2]) + b[i];
 
 
        WriteLn (b[n-1])
end.

[Klavdia]

Спасибо вам! А можно помочь с программой целиком??? Чтобы выполняла оба условия задачи.

[Serge_Bliznykov]

Сообщение от Klavdia

Спасибо вам! А можно помочь с программой целиком??? Чтобы выполняла оба условия задачи.

не хочу Вас расстраивать, но все предложенные варианты решения выполняют ОБА условия задачи: и находят минимальную суммарную длину и делают это БЕЗ ПЕРЕБОРА.

насколько я могу судить, используется т.н. "динамическое программирование".

[BDA]

Serge_Bliznykov, ТС имеет ввиду неполноту выходных данных.

[Poma][a]

не хочу Вас расстраивать, но все предложенные варианты решения выполняют ОБА условия задачи: и находят минимальную суммарную длину и делают это БЕЗ ПЕРЕБОРА.

насколько я могу судить, используется т.н. "динамическое программирование".

Входными данными являются число гвоздей и их координаты, выходными минимальная суммарная длина и пары соединений гвоздей.

Угу.. Не выводит..

[Serge_Bliznykov]

ТС имеет ввиду неполноту выходных данных.

ага. спасибо. тогда согласен, это действительно так, какие пары дают такую длину программа не сообщает...

p.s. это потому что в аналогичной задаче на ACMP требовалось одно число - только минимальная длина нити и ничего более!

[Вадим Мошев]

По рейкой понимается "одномерная доска", где гвозди можно вбивать только в ряд?
Зачем нужны тогда координаты?
И если я правильно понимаю, что такое рейка, то, если я не ошибаюсь, то оптимальное решение такое:
если число гвоздей чётное, то 1 соединяется во 2-м, 3 с 4, 5 с 6 и так далее.
Если нечётное, то так же, только предпоследний соединяется ещё и с последним.