Олимпиадная информатика - 2010

Задача «Новая школа»

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

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

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

Первая строка входного файла содержит число N - количество учеников в школе (1<N<500). Каждая из последующих N строк содержит координаты дома школьника - два целых числа из диапазона [-32767, 32767], разделенных пробелом.

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

Ваша программа должна вывести в выходной файл координаты места для постройки здания - два целых числа, записанных через пробел.

INPUT.TXT

4 0 0 0 0 1 1 2 2

OUTPUT.TXT

0 1

program aa;
 var bx,by,lx,ly,mx,my,j,b,i,n,m,k,d,c,h,a:longint;x,y:array[0..505] of longint;
   begin
 assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
  read(n,x[1],y[1]);		{Ввод количества учеников и координат первого дома}
  mx:=x[1];bx:=x[1];		{Первоначальные значения меньшего и большего значения по Х}
  my:=y[1];by:=y[1];		{Первоначальные значения меньшего и большего значения по У}
  for i:=2 to n do		{Перебор оставшихся домов}
  begin
   read(x[i],y[i]);		{Ввод координат очередного дома}
   if x[i]<mx then mx:=x[i] else if x[i]>bx then bx:=x[i];{Изменение граничных значений по Х}
   if y[i]<my then my:=y[i] else if y[i]>by then by:=y[i];{Изменение граничных значений по У}
  end;
  m:=50000000;			{Первоначальное значение наименьшей суммы расстояний по Х}
  for i:=mx  to  bx  do		{Перебор всех значений Х}
  begin
   d:=0;			{Обнуление суммы расстояний до текущей улицы}
   for j:=1 to n do
   d:=d+abs(i-x[j]);		{Накопление суммы расстояний до текущей улицы}
   if d<m then			{сравнение с текущей минимальной суммой}
    begin
     m:=d;			{Изменение текущей минимальной суммы расстояний}
     lx:=i;			{Изменение значения лучшей улицы по координате Х}
    end;
  end;
  m:=50000000;			{Те же дейсвия по координате У}
  for i:=my  to  by  do
  begin
   d:=0;
   for j:=1 to n do
   d:=d+abs(i-y[j]);
   if d<m then
    begin
     m:=d;
     ly:=i;
    end;
  end;
  write(lx,' ',ly);		{Вывод результата - лучших значений по Х и по У}
 close(input);close(output);
end.



close
 

Разбор задачи №3 "Новая школа"

Для каждой точки города найдем сумму расстояний до места проживания каждого школьника и выберем ту, где эта сумма минимальна. Хранить в памяти весь двумерный массив [-32767..32767, -32767..32767,] нецелесообразно. Оптимизируем решение. Во-первых сразу понятно, что располагать школу западнее (левее) самого западного (левого) дома с детьми, восточнее самого восточного , южнее самого южного или севернее самого северного невыгодно.

о координатах запомнить максимум и минимум для каждой из их координат и ограничим перебор этими пределами. Во- вторых, координаты оптимального места расположения школы не зависят одна от другой. Расстояние в городе между 2 точками (a;b) и (c;d) равно |a-c|+|b-d|. Мы стремимся минимизировать сумму расстояний от точки (х;у) до точек (a 1 ; b1), (a2;b2),.. (an ; bn). Эта сумма равна (|х- a 1 |+|y - b1|)+ (|х- a 2 |+|y - b2|)+… +(|х- a n |+|y - bn|) = (|х- a1 |+|х- a 2 |+…. +|х- a n |) + (|y - b1|+| y - b2|+… |y - bn|).

Выражение, стоящее в первых скобках никак не зависит от значения выражения во вторых скобках.

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

Возьмём первоначально сумму расстояний заведомо большую любой возможной, на пример М= 70000*500 (70000 заведомо больше самого большого расстояния по одной координате, 500 – предельное значение количества школьников).

Подобная задача (алгоритм тот же самый) несколько лет назад предлагалась на ЗОНАЛЬНОМ туре олимпиады под названием «Мэрский дом». То, что содержание задачи переработано – это хорошо. Но имеем ещё одно подтверждение того, что сложность для РАЙОННОГО тура завышена.