Хоровод. Олимпиадная задача

#cpp #c #алгоритм

Возникла проблема с решением данной задачи. Я не прошу написать решение задачи, подскажите
алгоритм решения, этапы. Спасибо.

Задание
Традиция водить хороводы - один из самых древних обычаев на Руси. Хороводы напоминают
солнце. Свою историю они ведут еще со времен славян, прославляющих Ярило. Наши предки
водили хороводы вокруг реликтовых деревьев и исполняли сакральные песни.
Новогодний хоровод - традиция старая, ей уже больше двух веков. В дореволюционной
России детей собирали вокруг елки, тогда-то и исполнялась главная песня.
В хороводе обычно участвует 2N человек, которые равномерно распределяются по окружности
радиуса N/π. Среди участников хоровода есть К  Дедов Морозов. Естественно, каждый хочет
оказаться как можно ближе к Деду с подарками. Попробуйте и вы найти такое положение
в хороводе, чтобы сумма расстояний по дуге до всех Дедов Морозов была минимальной. 
Формат входных данных
В первой строке входного файла записаны два числа N и К. (1 ≤ N ≤ 10; 1 ≤ K < 2N).
Во второй строке записано К чисел - номера точек на окружности, в которых стоят Деды
Морозы. Точки пронумерованы по часовой стрелке.
Формат выходных данных
В выходной файл выведите минимальную сумму расстояний по дуге от оптимального положения
до всех Дедов Морозов. 
    

Ответы

Ответ 1

Идея: рассмотрим функцию F_i(n) = расстояние до i-го Деда в зависимости от текущей
позиции.
Эта функция (рассматриваемая как функция действительного аргумента) является непрерывной
и кусочно-линейной. Расстояние с каждым шагом либо уменьшается на единицу (если мы
двигаемся по кратчайшей дуге к выбранному Деду), либо растёт (если от него). Мы видим,
что у функции ровно две точки перелома: (1) позиция Деда, (2) диаметрально противоположная
позиция.
Далее, функция, которую мы минимизируем -- сумма таких функций. Сумма кусочно-линейных
функций тоже, очевидно, кусочно-линейна, так что оптимального значения она достигает
в точке перелома (или если мы ищем на сетке, то рядом с ней) или на концах области
определения. Поскольку точки перелома всех F_i мы знаем, знаем и точки перелома их
суммы. Их всего не более 2*К штук.
Итак, для поиска минимального значения достаточно перебрать целые точки около точек
перелома, плюс первую/последнюю точки, количество проверок O(K), каждая проверка O(K),
итого O(K^2).


Ответ 2

Первое, что приходит на ум, это считать расстояние (в градусах) между каждыми двумя
участниками хоровода. Оно равно 360/(2N). Далее вам необходимо просто последовательно
перебирать людей в хороводе (точки) и, если текущая точка не Дед Мороз, то искать расстояние
по дуге до каждого деда мороза в хороводе опираясь на известное расстояние в градусах
между двумя ближайшими участниками:
1. находить градусную величину угла (обозначим переменной "DEG") между каждым Дедом
Морозом и участником. 
2. находить расстояние до Деда мороза по дуге: 2п * (N/п) * DEG/360, 
    ( где DEG - угол, п - 3.14(число ПИ) ).

Ну, а далее, уже "дело техники" :)


Ответ 3

Могу предложить примитивный супер-нубский алгоритм:
Имеется закольцованный список. Для каждой позиции заводим счётчик = 0 (далее i) и
результат = 0 (далее result), затем циклом или рекурсивно отходим налево и направо
(на ++i позицию). Если левая или правая позиция = дед мороз, то result += i * (не забыть
приплюсовать дважды, если два деда мороза). Если левая рассматриваемая позиция равна
правой, то закончить рассмотрение данной (начальной) позиции и перейти к следующей.
Таким образом нужно рассмотреть все позиции и выбрать ту, где наименьший result.
* Т.к. вам нужно сосчитать не количество позиций, а реальное расстояние, придётся
ввести функцию рассчёта расстояния от рассматриваемой позиции до позиции i. И в result
нужно будет складывать не i, а эти самые расстояния.
Оговорюсь сразу, что выполняется слишком много лишних рассчётов. Я уверен, что, опираясь
на результаты одних вершин, можно получить результаты для других, минуя лишние рассчёты,
но это уже на вашей совести. Считаю такой алгоритм приемлемым, т.к. количество человек
меньше 20, соответственно долгих рекурсий и циклов не будет.


Ответ 4

Посчитать для любой точки I сумму расстояний S и кол-во ДедМорозов в левой и правой
полуокружности - K1 и K2=K-K1. При проходе по час.стрелке от I : I=(I+1) mod N расстояние
до каждого правого уменьшается на 1, до левого увеличивается на 1, соот-во S мен-ся
на +K1-(K-K1)=2*K1-K
Когда I или (I+N/2)mod N проходят точки K[J] (ДедМорозов) соот-во делать K1=K1+1
и K1=K1-1. 
Если I!=K[J] (не ДедМороз) сверять S с прежним максимумом
При правильной реализации время работы O(N)