input,output

[Ainash]

Приветствую всех!!! Нужна помощь )))

[Abstraction]

Вы бы условия хоть вкратце обозначили. И текст выложили хотя бы в rtf.
Задачи хорошие, добрые. Пятую, похоже, упростили на ходу, а изначально там было что-то вроде поиска пути по графу.

1. "Гвоздики"
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Входные данные. В первой строке входного файла INPUT. IN записано число N – количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел -координаты всех гвоздиков (неотрицательные целые числа,не превосходящие 10000).
Выходные данные. В выходной файл OUTPUT. OUT нужно вывести единственное число -минимальную суммарную длину всех ниточек.
Пример входного и выходного файлов:

INPUT. IN               | OUTPUT. OUT
5                       |
4   10    0    12    2  |  6

Первое действие: прочитать координаты и упорядочить их по возрастанию.
Второе действие: гм... наверное, имеет смысл начать с левого гвоздика. Он соединяется однозначно. Но вот третий слева гвоздик, как мы видим в примере, можно привязывать как к левому, так и к правому.
Базовая идея: если мы в какой-то момент привязали все гвоздики до n-ного одним и другим способом, то для дальнейшей привязки нам нужно из этих способов выбрать тот, где суммарная длина ниток минимальна (как в этой статье, например). Но вот по дороге нам придётся анализировать разные варианты, составляя из них список.

Какие мысли и/или код есть у Вас?

[puporev]

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

[lex_kz]

Всем привет у меня такая же проблема!! Вообщем это задачки с олимпиады школьной,нужно до завтра решить,а я в Паскале не тудым и не сюдым,как говорится.Занимался только pawn скриптингом в gta а вот паскаль могу только по примеру листинга делать..помогите пожалуйста,ребят очень прошу...у меня всего 3 задачи,вот они

[Ainash]

да, конечно

[Serge_Bliznykov]

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

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

не, имхо не всё так просто...

Перво-напервно, крайние гвоздики должны быть соединены вне зависимости от длины.
т.е. после сортировки по координатам. 1-й гвоздик соединить со 2-м.
а N-й - соединить с n-1
это как бы очевидно... (ну или мне кажется, что это очевидно...)

а вот как дальше среди оставшихся "непривязанными" уже искать миниальное расстояния и привязывать - я, например, лично, в небольшом затруднении..

[Костя КС]

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

крайние гвоздики должны быть соединены вне зависимости от длины.

Всего соединений будет :
если гвоздиков четное число, то abs(n/2)+1
если гвоздиков нечетное число, то abs(n/2).

Т. к. мы всегда будем соединять 1ый со 2ым и Nый c (N-1)ым, то остается подсчитать разницы в координатах между каждыми гвоздиками от 2го до (N-1)ого и выбрать из них минимальные.

Например, если у нас 5 гвоздиков, то всего соединений 3. соединив 1 и 2, 4 и 5, останется выбрать одно минимальное между 2-3-4.

[Serge_Bliznykov]

если гвоздиков четное число, то abs(n/2)+1
...
соединив 1 и 2, 4 и 5, останется выбрать одно минимальное между 2-3-4.

Вот я и пытаюсь донести, что соединений может быть как N/2 так и (N div 2)+1.. (кстати, зачем у Вас в формуле модуль? abs() ? )

Давай-те рассмотрим несколько простых конкретных вариантов, когда число гвоздиков чётное и равно 6.
1
Возьмём 6 гвоздиков с координатами: 1 2 4 7 9 10 очевидно, что минимальное потребуется 3 ниточки общей длиной 5

2
Возьмём 6 гвоздиков с координатами: 1 2 4 8 10 11 очевидно, что минимальное потребуется 4(или 3) ниточки общей длиной 6

3
Возьмём 6 гвоздиков с координатами: 1 2 4 9 11 12 очевидно, что минимальное потребуется 4 ниточки общей длиной 6

p.s. т.к. N по условию задачи меньше или равно 100, а соединять ниточками надо всегда ближние гвоздики, то, имхо, нет никаких проблем в написании полного перебора... Это точно даст наименьшую суммарную длину соединений, но, скорее всего (я даже почти уверен в этом) даст неоптимальную вычислительную загрузку..
Имхо, правильный ответ крутится где-то вокруг выбора минимальных расстояний.. Или динамического программирования...

[val_nnm]

Тут действительно не всё так просто. (Я и сам изначально думал про полный перебор или про метод ветвей и границ)
Например для 12 гвоздиков с кординатами
1 2 3 4 5 6 7 8 9 10 11 12 оптимальным будет
1-2 3-4 5-6 7-8 9-10 11-12
(6 ниточек общей длинной 6)
Но если задать другие кординаты
1 2 3 10 11 12 20 21 22 30 31 32
1-2-3 10-11-12 20-21-22 30-31-32
(8 ниточек общей длинной 8)



Теперь начну рассуждения. (везде в дальнейшем буду рассмтривать кординаты гвоздиков упорядоченные в возрастающем порядке)
Оптимальное соеденение гвоздиков будет состоять из групп по 2 или по 3 гвоздика подрят (группы несвязанны между собой)
(если кому-то очень, очень, очень нужно доказательство то могу его написать, но поверьте на слово любое другое соединение гвоздиков можно разбить на группы по 2 или 3 соединенных гвоздика при этом уменьшив длину необходимой нити)
Тогда можно сказать что оптимальным решением будет некоторый набор из групп по 2 или 3 связанных вместе гвоздиков. Где сумма гвоздиков равна количеству гвоздиков в доске. Причём нужно выбрать группы так чтобы сумма длин всех нитей была минимальной.
Нарисуем граф. Каждый узел будет обозначать, сколько гвоздиков уже связанно (см. рисунок)
Красным цветом нарисованы ребра для соеденения 2 гвоздиков. Зелёным цветом – для 3 гвоздиков.
(узел 1 нарисован серым т.к. 1 гвоздик соединить невозможно)
Теперь это уже простейшая задача на нахождения минимального пути на графе из узла 0 в последний узел (на рисунке узел 9).
В вкратце опишу своими словами алгоритм поиска (есть куча различных описаний в разных книгах).
Будем проходить по очереди, по всем узлам начиная от 0. Для каждого узла будет записывать минимальный путь (минимальную необходимую длину нити). Т.е. берём минимальный (уже записанный) путь для каждого из предыдущего узла связанного с данным 1 ребром прибавляем путь, добавляемый каждым ребром, выбираем из них минимальный и записываем его для текущего узла. И.т.д. для каждого узла пока не будет достигнут последний узел. Путь, записанный для него и будет решением данной задачи.

Реализация.
Обозначил X[1]..X[n] координаты гвоздиков отсортированные по возрастанию.
L[0]..L[n] минимальная необходимая длинна нити.
Тогда L[0]=0 L[1]=неопределенно (можно задать равным бесконечности)
L[2]=L[0]+X[2]-X[1]=X[2]-X[1] L[3]=L[0]+X[3]-X[2]+X[2]-X[1]=X[3]-X[1] L[4]=L[2]+X[4]-X[3]
А дальше L[i]=min(L[i-3]+X[i]-X[i-2],L[i-2]+X[i]-X[i-1])
Когда дойдём до L[n] это и будет решением.
В принципе можно несоздаваь весь массив L[0]..L[n] а хранить только последнии 3 числа (т.е. использовать только 3 переменные вместо массива L). Но это уже сами.