Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-11-22 | 1027 |
5.00
из
|
Заказать работу |
|
|
Вдоль прямой дороги расположены деревни. Дорога представляется целочисленной осью, а расположение каждой деревни задается одним целым числом – координатой на этой оси. Никакие две деревни не имеют одинаковых координат. Расстояние между двумя деревнями вычисляется как модуль разности их координат.
В некоторых, не обязательно во всех, деревнях будут построены почтовые отделения. Деревня и расположенное в ней почтовое отделение имеют одинаковые координаты. Почтовые отделения необходимо расположить в деревнях таким образом, чтобы общая сумма расстояний от каждой деревни до ближайшего к ней почтового отделения была минимальной.
Задание
Напишите программу, которая по заданным координатам деревень и количеству почтовых отделений находит такое расположение почтовых отделений по деревням, при котором общая сумма расстояний от каждой деревни до её ближайшего почтового отделения будет минимальной.
Входные данные
Первая строка входного файла POST.DAT содержит два целых числа: первое число – количество деревень V, 1≤ V ≤300, второе число – количество почтовых отделений P, 1≤ P ≤30, P ≤ V. Вторая строка содержит V целых чисел в возрастающем порядке, являющихся координатами деревень. Для каждой координаты X выполняется 1≤ X ≤10000.
Выходные данные
Первая строка выходного файла POST.SOL содержит одно целое число S – общую сумму расстояний от каждой деревни до её ближайшего почтового отделения для расположения почтовых отделений, описанного во второй строке. Вторая строка содержит P целых чисел в возрастающем порядке. Эти числа являются искомыми координатами почтовых отделений. Если для заданного расположения деревень есть несколько решений, то программа должна найти одно из них.
|
Пример входных и выходных данных
POST.DAT | POST.SOL |
10 5 1 2 3 6 7 9 11 22 44 50 | 9 2 7 22 44 50 |
ОЦЕНКА РЕШЕНИЯ
Если выходной файл не соответствует описанным требованиям – оценка 0. В противном случае, оценка будет вычислена по таблице 1 следующим образом: если найденная сумма – S, а минимальная сумма – Smin, то необходимо вычислить q=S/Smin и найти соответствующую оценку c в нижней строке.
q=S/Smin | q=1.0 | 1.0<q≤1.1 | 1.1<q≤1.15 | 1.15<q≤1.2 | 1.2<q≤1.25 | 1.25<q≤1.3 | 1.3<q |
c |
Решение
Program POST;
const MaxN = 350;
var k, n, p: integer;
x: array [1..MaxN] of integer;
d, t: array [1..MaxN] of longint;
pr: array [1..MaxN, 1..35] of integer; {объявление массивов}
procedure ReadAll;{процедура связи с файлом вход. данных и записи в файл}
var i: integer;
begin
Assign(input, 'post.dat'); Reset(input);
Assign(output, 'post.sol'); Rewrite(output);
Read(n, p);
for i:= 1 to n do read(x[i]); {цикл перебора элементов массива}
end;
procedure Solve; {основная процедура решения задачи}
var i, j, r, m: integer;
min, s: longint;
begin
fillchar(d, sizeof(d), 0); {заполняем строку нулями}
for i:= 1 to n do begin
s:= 0;
for j:= 1 to i-1 do inc(s, longint(x[i])-longint(x[j]));{увеличиваем значение переменной s и преобразовываем элементы массива в длинное целое}
d[i]:= s;
end;
for k:= 2 to p do begin
for i:= 1 to N do begin
t[i]:= 1000000000;
r:= i; {запись координат деревень }
s:= 0;
for j:= i-1 downto 1 do
begin
while (r > j) and (x[i]-x[r-1] < x[r-1]-x[j]) do begin {координаты почты }
dec(r);
s:= s - (longint(x[r]) - longint(x[j+1])) +
(longint(x[i]) - longint(x[r]));
end;
inc(s, longint(r-j-1) * (longint(x[j+1])-longint(x[j])));
if s + d[j] < t[i] then begin
t[i]:= s + d[j];
pr[i, k]:= j;
end;
end;
end;
d:= t;
end;
min:= maxlongint;
for i:= 1 to n do begin {вычисление минимального расстояния}
s:= d[i];
for j:= i+1 to n do inc(s, longint(x[j])-longint(x[i]));
if s < min then begin
min:= s;
m:= i;
end;
end;
writeln(min);
k:= p;
while k > 0 do begin
d[k]:= m;
m:= pr[m, k];
dec(k);
end;
for i:= 1 to p-1 do write(x[d[i]], ' ');
writeln(x[d[p]]);
end;
begin
ReadAll;
Solve;
end.
Тема: Работа с большими числами.
Задача 2: Светофоры
В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.
|
Формат входных данных
Имя входного файла input.txt
В файле INPUT.TXT записано два числа N и M
(0 < N<= 100, 0 <= M <= N*(N-1)/2). В следующих M строках записаны по два числа i и j (1<= i,j<= N), которые означают, что перекрестки i и j соединены тоннелем.
Формат выходных данных
|
|
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!