Олимпиадная задача!!! Сложная!!!!

← →
pumba (2002-12-08 09:11) [0]

В окрестностях Новосибирска решили провести Открытый чемпионат Мира по лыжным гонкам. Желающих участвовать в нем очень много (особенно многочисленные команды приедут из Сибири, Канады и Африки), поэтому необходимо в короткое время провести отбор основных участников. Это значит, что соревнования нужно проводить одновременно на нескольких лыжных трассах. В тайге разместили N баз, куда участников соревнований должен доставлять вертолет. Между этими базами необходимо проложить лыжные маршруты так, чтобы два разных маршрута не пересекались. Между двумя различными базами может проходить только один маршрут. Любой маршрут должен начинаться на одной базе, а заканчиваться на другой, не проходя при этом через третью.

Организаторов соревнований интересует, какое максимальное количество лыжных трасс можно проложить.

Входные данные
Во входном файле записано одно целое число N (2

← →
pumba (2002-12-08 09:42) [1]

!!!!

← →
Феу (2002-12-08 12:37) [2]

Сомневаюсь, что и правда сложная. Мне кажется, она сводится к нахождению максимального числа непересекающихся ребер между n узлами на плоскости. Навярняка есть на каком-нибудь математическом сайте. В одну формулу. При желании можно и самому прикинуть. (посчитай руками для 1, 2, 3 .. баз, и поищи такую последовательность на www.research.att.com/~njas/sequences)

← →
Fantasist (2002-12-08 19:37) [3]

> . Мне кажется, она сводится к нахождению максимального числа
> непересекающихся ребер между n узлами на плоскости

Да какой там. Тут и плоскости-то никакой нет - дано одно число, надо получить другое. Тут все просто 2 бызы - 1 маршрут, 3 базы - 3 маршрута, каждая последующая база добавляет по 3 маршрута.
Отсюда:
if N<1 then Result:=0
else
if N=2 then Result:=1
else
Result:=3*(N-2);

← →
esu (2002-12-08 20:54) [4]

На C класно решается.
void main(void)
{
int n = 6;
printf("%d\n", n < 1 ? 0 : (n == 2 ? 1 : 3*(n-2)));
}

← →
Hirara (2002-12-08 21:46) [5]

а я вот на лыжах катаюсь на горных

← →
Феу (2002-12-08 22:07) [6]

Да какой там. Тут и плоскости-то никакой нет - дано одно число, надо получить другое. Тут все просто 2 бызы - 1 маршрут, 3 базы - 3 маршрута, каждая последующая база добавляет по 3 маршрута.
Сам уже допер. Впрочем, я и говорил про "в одну формулу". Все остальное - теоретическая база (i.e. понты).
А вот как там Пумба? Получил чего?

← →
Дмитрий К.К. (2002-12-08 22:09) [7]

Особенно большие шансы на победу на чемпионате мира по лыжным гонкам имеют спортсмены из Африки ;)

← →
Мазут Береговой (2002-12-08 23:36) [8]

Ну... за наших младших братьев... из Африки...

← →
zavdim (2002-12-09 11:40) [9]

Формула абсолютно не верна.
Для 4 - она идет.
А нарисуй как ты проложишь 9 трасс для пяти баз?

← →
zavdim (2002-12-09 11:41) [10]

хотя звиняюсь - вроде верно.

← →
ZZ (2002-12-09 12:52) [11]

printf("%d\n", n < 1 ? 0 : (n == 2 ? 1 : 3*(n-2)));
n = 4 => 3*(4-2)=3*2=6?? Может кто изобразит в прямоугольнике 6 НЕпересекающихся трасс?

← →
zavdim (2002-12-09 13:23) [12]

В условии не сказано, что маршруты - прямые.
Поэтому можно.
Формула верная - доказать можно.

← →
DarkGreen (2002-12-09 14:40) [13]

5 баз расположи на одной линии и проведи между ними 9 трасс, по моему только 4 получится. Т. е. условия задачи либо не полны, либо не корректны

← →
DarkGreen (2002-12-09 14:43) [14]

Сорри, не увидиел предудущий постинг.

← →
DarkGreen (2002-12-09 14:43) [15]

Сорри, не увидиел предыдущий постинг.

← →
zavdim (2002-12-10 07:02) [16]

А вот насчет доказательства - как?
Есть идеи?

← →
Fantasist (2002-12-10 21:19) [17]

> А вот насчет доказательства - как?
> Есть идеи?

А что тут сложного.
Вначале аксиома: так как линии, которыми мы соденяем точки(базы) не обязательно прямые, то для любого множества точек мы можем взять любые три из этих точек и построить на них такой "треугольник" с не прямыми ребрами, что все остальные точки окажутся внутри этого треугольника. В дальнейшем под "треугольником" будем понимать такой треугольник у которого ребра - не обязательно прямые.
Для двух и одной базы все очевидно.
Возмем три базы. Строим на них треугольник - это три маршрута. Добавим базу внутрь этого треугольника. Очевидно, что из этой новой базы мы можем провести три линии: по одной к каждой вершине треугольника - это еще три маршрута. Этими тремя линиями, мы разбили исходный треугольник на три треугольника. Добавление любой базы внутрь любого из треугольников - даст нам еще три маршрута и три треугольника и т. д. для любого количества баз.
Вернемся к трем базам и добавим базу снаружи треугольника. Но мы можем взять эту новую базу и построить такой треугольник, что одна из предидущих баз окажется внутри этого треугольника(остальные две буду вершинами). Значит добавление базы снаружи треугольника равносильно тому, как будто мы добавили одну из предидущих баз внутрь нового треугольника. Случай с добавлением внутрь уже рассмотрен.

Не строго, но идея понятна.

← →
maxo (2002-12-10 23:01) [18]

на самом деле всё уже доказано это изучают на первом курсе
Дисциплина: Дискретная математика
Раздел: Теория графов

Олимпиадная задача!!! Сложная!!!! Найти похожие ветки