Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-11-22 | 1028 |
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 соединены тоннелем.
Формат выходных данных
|
|
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!