Задача 1. Почтовые отделения.

Вдоль прямой дороги расположены деревни. Дорога представляется целочисленной осью, а расположение каждой деревни задается одним целым числом – координатой на этой оси. Никакие две деревни не имеют одинаковых координат. Расстояние между двумя деревнями вычисляется как модуль разности их координат.

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

Задание

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

Входные данные

Первая строка входного файла 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, а минимальная сумма – S_min, то необходимо вычислить q=S/S_min и найти соответствующую оценку 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 соединены тоннелем.

 

Формат выходных данных