Удалить минимальное количество лопастей

Question

Недавно я столкнулся с этой проблемой на интернет-судье Timus. Для людей, не желающих нажимать на ссылку. Вопрос в следующем:

Опытные участники чемпионата Урала приезжают в Екатеринбург заранее, чтобы привыкнуть к суровым погодным условиям, прогуляться по городу и, конечно же, посетить аквапарк "Лимпопо". Мало кто знает, что рядом с аквапарком есть завод № 404, и местные жители называют его "Ошибка 404". Растение не так легко найти, и еще сложнее узнать, что там происходит. К счастью, наблюдать за растением можно с близлежащего пешеходного моста. Из-за кажущейся неподвижности и запустения растения можно подумать, что оно не работает, но это не так. Основным направлением работы завода является ремонт авиационных двигателей. Некоторое время назад завод получил заказ на ремонт сломанного газотурбинного двигателя. Оказалось, что некоторые лопасти были оторваны, что привело к избыточной нагрузке на вал двигателя. Специалисты на заводе решили, что двигатель можно быстро отремонтировать, удалив некоторые из неповрежденных лопаток, чтобы центр масс оставшихся лопаток снова оказался на оси вращения. Для поддержания максимально возможной мощности двигателя необходимо удалить минимальное количество лопастей. Необходимо оставить хотя бы одно лезвие, иначе двигатель не будет работать вообще. Эксперты утверждают, что, когда все лезвия были целы, их конечные точки образовывали обычный n-угольник. Скажите им, какие лезвия должны быть удалены.

> Input The first line contains the initial number of blades in the
> turbine n and the number of torn blades k (3 ≤ n ≤ 20000; 1 ≤ k ≤ n −
> 1). The integer n has at most two distinct prime divisors. The next
> line contains k integers, which are the numbers of the torn blades in
> ascending order. The blades are numbered from 1 to n clockwise. 
Output
> In the first line output the minimum number of blades that should be
> removed. In the second line output the numbers of these blades in any
> order separated with a space. If several answers are possible, output
> any of them. If it is impossible to repair the engine by removing some
> of the blades, output “−1”. 
> 

У меня проблемы с настройкой этой проблемы. Моя первоначальная мысль заключается в том, что, поскольку необходимо восстановить центр масс, сломанный клинок должен быть окружен равным количеством не сломанных клинков.

Таким образом, если мы представим сломанный блейд как 0, а неразбитый блейд как 1, конкретная конфигурация может быть представлена ​​как: 011

Я не уверен, что нахожусь на правильном пути, и некоторые отзывы будут полезны при попытке понять эту проблему.

Спасибо

Answer 1

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

Кончики лезвий являются nкорни единства, кончик клинка k я сидела

z_k = e^(2\pi i * k/n)

Центр масс после снятия лезвий k1, ... , kr находится на оси вращения, если и только если

z_k1 + z_k2 + ... + z_kr = 0

Теперь позвольте 1 < d < n быть делителем n, Лезвия k1 + m*d, 0 <= m < n/d образуют вершины правильного n/dугольник. Таким образом, удаление их всех оставляет центр масс на оси вращения.

Стратегия состоит в том, чтобы попытаться покрыть список индексов сломанных лопастей набором непересекающихся регулярных d_i, где d_i является делителем n, Итак, в списке найдите пары, индексы которых отличаются на делитель n,

Answer 2

Моя первоначальная мысль заключается в том, что, поскольку необходимо восстановить центр масс, сломанный клинок должен быть окружен равным количеством не сломанных клинков.

Нет. Пропеллер должен быть вращательно-симметричным. Если одно лезвие оторвано от 3-лопастного пропеллера, его невозможно перецентрировать.

Ключевые моменты:

1. Эксперты утверждают, что, когда все лезвия были целы, их конечные точки образовывали обычный n-угольник.

2. Целое число n имеет не более двух различных простых делителей.

Начните с чего-то простого, что соответствует этим двум свойствам, например, декагон. Задайте себе вопрос: как соотносятся полигоны и симметрия? Как тогда делители 10 относятся к многоугольникам и симметрии? Чтобы упростить вещи, можете ли вы представить эти многоугольники, используя скаляры, а не двумерные точки? Подсказка: модульная арифметика играет в решение.

Изображения конфигурации лезвий (как нефиксированные, так и фиксированные) должны помочь. Например:

        2 2 2 2           
    3 1 1                                                 
  4 0 4 0 4 0 4 0     

  5 9 5 9 5 9     
    6 8 6 8 6 8 8       
        7 7 7 7           
   целых 10 гон 2 сломанных лезвия 3 сломанных лезвия 3 сломанных лезвия

Есть два возможных решения для 2 сломанных лезвий и первых 3 сломанных лезвий, хотя только одно является оптимальным для каждого. Второй 3-битный имеет одно решение. Ищите полигоны.

Answer 3

Эта проблема действительно очень сложна математически, но ее можно упростить, если понять, как работает балансировка.

• Если число лопастей "n" является простым числом, нет другого решения, кроме как удалить все лопасти. Невозможно восстановить баланс даже одного отсутствующего клинка, когда n - простое число. Если нет решения для одного блейда, не будет решения для нескольких пропавших без вести.
• Если число лопастей "n" не является простым, то по определению (и согласно правилу этой задачи) это произведение двух простых чисел "p1" и "p2", пример: для 21 лопастей, p1=3, р2=7.

Если одно лезвие "k1" отсутствует, баланс будет получен, когда будет удалено в общей сложности "N/p2 (пример =3) ножей, расположенных на равных расстояниях (визуализируйте знак Mercedes Benz). Если два лезвия" k1 "и" k2 " отсутствуют, баланс будет получен, выполнив точно для "k2", как в предыдущем случае, ЗА ИСКЛЮЧЕНИЕМ, если k1 и k2 разнесены в соответствии с симметрией "p1" или "p2"

Примеры с 12 и 20 блейдами усложняют понимание, потому что они кратны 4, что означает две симметрии порядка 2. Я предпочитаю примеры с 21 блейдом, у которых нет этой проблемы.

1. 21 лезвие, один отсутствующий лезвие k1 = 1 -> Баланс получается удалением лезвий 8 и 15 (симметрия p1 - порядок 3)
2. 21 лезвия, два отсутствующих лезвия k1=1, k2=2 -> Баланс получается удалением лезвий 8 и 15 для k1 и 8 и 16 для k2
3. 21 лезвие, два отсутствующих лезвия k1=1, k2=8 -> так как k2-k1=7, тебе просто нужно удалить лезвие 15, чтобы завершить баланс
4. 21 лезвия, два отсутствующих лезвия k1=1, k2=7->, поскольку k2-k1=6 = 2*3, можно заметить, что лезвия имеют симметрию порядка 7, поэтому можно завершить рисунок, удалив лезвия 4,10,13,16,19, чтобы получить идеальный баланс. Но что интересно, вы также можете рассматривать это как пример №2 и использовать в два раза больше симметрии порядка 3; таким образом, есть также решение, удаляя лезвия 8 и 15, чтобы уравновесить k1, и 14 и 21, чтобы уравновесить k2.

Поэтому, чтобы решить вашу проблему, ваш алгоритм должен сделать следующее: - Если n - простое число, просто выведите "-1" - нет решения - Начиная с первого отсутствующего блейда, сканируйте группы отсутствующих блейдов с интервалом "n/p1 (= 7)"и"n/p2(=3)" . Подсчитайте, сколько групп в каждой группе симметрии есть, и сколько блейдов вам нужно заменить.

• В этом примере ваше решение первого порядка просто:
  Количество удаляемых лопастей будет (количество групп симметрии p1) *7 + (Количество групп симметрии p2)*3 - количество отсутствующих лопастей. Вам придется обработать исключения, подобные показанным в примере 4, где лучше обрабатывать лезвия по отдельности, но вы получите картину.