Wataru

У вас две большие ошибки с языком питон. Вы в цикле в alg итерируетесь по списку add, меняя его. Так делать нельзя. Ломаются итераторы и вы пропускаете половину элементов.

Вместо этого используйте цикл while:

while add:
  item = add[0]
  add.remove(item)
  s.append(item)
...

Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

С этими двумя изменениями должно работать. Ну, и у вас главная оптимизация алгоритма не реализована. Надо в начале цикла проверить, что среди оставшихся вершин в add есть хоть одна соединенная с каждой вершиной из exists. Если таковых нет - нужно вывалится из цикла.

Еще по коду:
range(n) в python возвращает 0..5. У вас там цикл по ребрам в __main__ и там идет обращение к i-1 в массиве graf. Т.е. обращение к [-1]. Вряд ли вы это хотели. Работает по чистой случайности, потому что в питоне a[-1] дает последний элемент.

И вообще, вы матрицу смежности строите, но нигде не используете.

Вместо функции check(), вы сделайте нормальный список смежности один раз, а то просто глаз режет от неоптимальности.

neighbors = [[] for i in range(count_vershin)]
for edge in graf:
  neighbors[edge[0]-1].append(edge[1]-1)
  neighbors[edge[1]-1].append(edge[0]-1)

Надо использовать более умный и быстрый алгоритм. Вы после каждой помены за O(n) проверяете, что массив отсортирован. когда как можно делать это за O(1) - ведь массив меняется всего в двух местах.

Для понимания алгоритма, сначала сделаем немного другую версию за O(n), а потом соптимизируем до константы.
Вы вместо сравнения с сортированным массивом пройдитесь по массиву и смотрите, что для всех соседних элементов следующий более или равен предыдущему.
Следующий шаг - заведите массив bool на n-1 элемент и храните в нем пометки, что в данной позиции массив отсортирован. При помене местами двух элементов надо пересчитать 4 позиции в этом массиве. Потом пройдитесь по массиву и проверьте, что там все элементы true. Пока все еще работает за линию и еще хранит лишний массив.
А теперь последний шаг - можно не проходиться по массиву bool каждый раз, если поддерживать счетчик, сколько там истинных элементов. После ввода массива list надо будет заполнить массив bool-ов и подсчитать, сколько там true. При перестановке a и b у вас максимум 4 элемента в массиве bool могут поменяться. Вот при этих изменениях вы счетчик пересчитывайте. Просто тупо при каждой записи в этот массив вычтите 1 из счетчика, если текущее там значение true и прибавьте 1, если новое значение true.

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

Но она обладает замечательным свойством - если состояние игры можно разложить на несколько независимых игр и игорк в свой ход может сделать ход в любой из игр, то функция Гранди может быть подсчитана как xor значений для всех состояний. По умному это называется, что игра является суммой игр. В некоторых задачах это позволяет колоссально сократить простарнство состояний.

Один пример - игра Ним. Есть несколько кучек камней. За свой ход игрок может взять сколько угодно камней из любой кучки. Проигрывает тот, кому не останется камней. В простом переборе вам придется в качестве состояния хранить вектор количеств камней в каждой кучке. Но ведь тут стостяние очевидно раскладвается на под-игры: каждая кучка - своя отдельная игра. Причем, функция Гранди тут тривиальна - это просто количество камней. Вот и получается решение игры Ним - взять xor размеров всех кучек. Если не 0, то состояние выгрышное. Надо взять из какой-то кучки столько камней, чтобы получился xor, равный 0.

Еще пример - есть плитка шоколада. Игроки ее ломают вдоль клеток. За свой ход игрок может взять любой прямоугольный кусок и разломить его как-то вдоль клеток (если там более 1x1 клеток, конечно). Проигрывает тот, кто не сможет сделать ни одного хода. Опять же, при простом переборе пришлось бы хранить в состоянии размеры всех кусоков. Тут ОЧЕНЬ много вариантов. А с функцией Гранди - достаточно рассмотреть состояния вида "одна плитка размера n x m". После одного хода у вас будет 2 плитки, но меньшего размера. Вы уже знаете для них функцию гранди, XOR'ите их и получаете функцию для возможного перехода.

Во-первых, берите две соседние стороны многоугольника. Если они коллинеарны, то берите другие 2 соседние. Но по хорошему, у вас коллинеарных соседних строн быть не должно и их можно объеденить при вводе полигона.

Но все-равно остается вопрос, а вдруг нормаль смотрит в сторону отчки (0,0,0).
Постройте уравнение плоскости ax+by+cz+d=0. (a,b,c) - это ваш найденный вектор нормали. d высчитывается, если подставить одну любую точку полигона.

Теперь, если d положительно, то точка (0,0,0) лежит в том полупространстве, куда смотрит вектор и вам надо развернуть нормаль.

Тут используется свойство знакового расстояния. Можно в уравнение плоскости подставить любую точку. Вы получите 0 для плоскости, положительные числа для одного полупространства и отрицательные для другого. Положительные в той части, куда торчит вектор нормали (ведь если отложить от точки на плоскости эту нормаль, и подсчитать знаковое расстояние, то получите тупо длину вектора нормали).

Это не совсем ним (где несколько кучек и за ход можно взять сколько угодно камней). Судя по коду, игроки могут брать 1,2 или 3 камня и кучка одна. Кажется, у вас выигрывает тот, кто возьмет последний камень.

Сначала немного теории игр.
Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

Поэтому для 8 камней, если начинает бот, и человек действует правильно - бот всегда проиграет.

Правильная функция choize должна быть:

def choose(s):
  if s%4 == 0: return 1
  else return s%4

Тогда бот обязательно выиграет, если выигрышная позиция есть, или если человек допустит ошибку, хоть у него и была выигрышная стратегия.

Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

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

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

Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

Обход других ботов делается так - у ботов есть подсчитанные пути. Боты пытаются сделать маленькие шаги вдоль пути. Если они пересекаются с другим ботом, то можно пропустить ход, или попытаться толкнуть другого бота. Расствьте ботам случайные приоритеты и, если бот с большим приоритетом хочет пересечься с ботом с меньшим приоритетом, то второй делает шаг назад.

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

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.

Я придумал решение через динамическое программирование.

Предположение - цены у каждого поставщика не возрастают при увеличении количества заказов. В противном случае, это бред какой-то, а не поставщики.

Ключевое наблюдение - если есть какой-то ответ (распределение заказов по поставщикам), то среди всех активных поставщиков всегда есть кто-то один, у которого текущая цена минимальна. Можно скидывать ему товары от остальных, пока не упремся в границу переключения цены у них. При этом цена у этого поставщика может еще и улучшиться. Общая сумма только улучшиться от этого. Если упремся в запасы этого поставщика, то можно его исключить из рассмотрения и повторить операцию. Таким образом, лишь улучшая ответ, мы придем к тому, что какие-то поставщики продают весь свой запас целиком, какой-то один продает сколько-то (и его цена меньше всех оставщихся). Все оставшиеся продают ровно минимальное количество для какой-то цены (ключ из входных данных). Можно в массив цен у каждого поставщика дописать вариант => <последняя цена>, если там такой записи еще нет. И еще запишите туда 0 => 0 в начало (купить 0 за 0). Тогда все еще упрощается - все поставщики, кроме одного, продают ровно какой-то свой priceBreak штук.

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

Это уже можно свести к чему-то вроде задачи о рюкзаке. Переберите одного особого поставщика (который будет продавать не фиксированное количество штук). Исключите его из массива поставщиков (но запомните его цены, чтобы считать, сколько ему придется заплатить за остаток).

Теперь, как в задаче о рюкзаке, считайте динамическое програмимрование DP(i,j) - какая минимальная цена, чтобы набрать ровно i штук у первых j заказчиков (и каждый продает ровно какой-то свой priceBreak).

База тривиальна: DP(0,0) = 0, DP(i>0, 0) = infinity (на практике - большое число, или -1 и это значение надо отдельно проверять при переходе).

Переход:

DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

Тут мы просто перебираем, сколько продает последний поставщик. Берем оставшиеся у предыдущих (DP(...,j-1) и прибавляем, сколько заплатим последнему.

Вот, подсчитали вы ДП. Теперь ответ - min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Перебирайте, сколько вы купите у особого поставщика. Берите оставшееся из динамического программирования.

Если поставщиков M, надо купть N штук, у каждого поставщика по K цен, но это решение будет O(M*(M*N*K + N)) по времени и O(M*N) по памяти. (На самом деле, можно уточнить оценку по времени- O(M*(M*N+N*L+N)), где L - общее количество записей в массивах цен у всех поставщиков).

Для восстановления ответа вместе с DP() запоминайте, какое значение k выдало лучший результат. Потом можно будет с конца размотать оптимальный ответ, выдавая известное значение последнему поставщику.

Если цены у поставщиков могут возрастать при увеличении количества, то решение остается в силе, только надо дописать в каждый массив "количество=>цена" элементы с количеством на 1 меньше каждого priceBreak. Потому что теперь в любом ответе все-равно можно будет перекидывать от одного заказчика к другому, пока не упремя или в priceBreak сверху, или в последнее количество с неменяемой ценой. И опять получается, что только один поставщик будет продавать не фиксированное в массиве значение.

Можно вместо ДП гнать симплекс метод, как Philipp уже написал (будет быстрее, если поставщиков мало, а количесто штук очень большое).

Возможно, можно ускорить решение в M раз, если вместо M разных ДП гнать одно со всеми поставщиками. Потом перебрать i<=n, распределить i штук по поставщикам беря только priceBreak, а потом прибавить остаток к поставщику с минимальной ценой (не переваливая за следующий priceBreak!). Но я не уверен, что это будет работать (не смог пока доказать, что, если у оптимального ответа урезать торчащий от priceBreak хвост у кого-то поставщика, то ответ останется оптимальным для нового количества).

Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех i, j проверяйте, что a[p[i]][p[j]] == b[i][j].

Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

Как только нашли перестановку, для которой матрицы совпали - выводите перестановку в ответ и вываливайтесь из перебора.

Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).

Алгоритм обхода в ширину или в глубину. Еще его называют алгоритм заливки. Гуглите. Если за одну заливку вы закрасили все черные пиксели, то фигура одна. Иначе, если компонент взязности несколько - разрыв есть.

Я так понял, надо распараллелить? Посмотрите на OpenMP - работает в С/C++. Параллеленье очень просто делается - вставляете какие-то директивы в код, ключи компиляции и все работает.

Как решать задачу паралелльно: Разбейте всю строку на N (количество потоков) частей и каждый поток отдельно для каждой части найдет ответ внутри нее. А также две велечины: Самый последний символ '<', самый первый симовл '<' и вообще, есть ли они в этом куске.

Потом непараллельная часть, которая выберет лучшый ответ из N кусоков, а также проверит, какой есть самый длинный ответ распределенный по кускам. Для этого у вас все есть - вы знаете в каждом куске какой символ может быть началом <...> идущий в следующие куски и какой может быть концом. Надо еще рассмотреть случай, что в данном куске последний < левее первого > - тогда из этого куска отрезок <...> торчать не может. Иначе смотрите, где может левее начаться отрезок. Это все реализуется одним циклом на N итераций. Надо хранить последний символ < в предыдущих кусках, который пока не закрыт. Или закрываете текущим куском и сравниваете с ответом, или обрываете его (если кусок начинается с <) или продолжаете отрезок в следующий кусок.

Вам равноудаленные или наиболее удаленные точки? Это немного разные вещи.

Равноудаленные точки - это надо пересекать "серединные перпендикуляры" для каждой пары заданных точек и смотреть, что решение одна и та же точка. Самые удаленные - это посмотреть на пересечения всех пар серединных перпендикуляров, перпендикуляров с границами области, вершины области. Из всех этих точек выбрать наиболее удаленные от всех заданных.

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

Зачем вообще данные с сервера отображать на клиенте? Считайте все локально - и клики и прибавления по таймеру. Единственная причина, которую я могу придумать, зачем вам это может быть нужно - это борьба с читерами.

Для этого отправляйте раз в секунду все действия пользователя на сервер (клики, нажатия кнопок покупок бонусов). Сервер должен повторить всю логику (прибавить клики, автоматические таймеры, включить всякие бонусы, если очков хватает) и отправить назад результирующие очки пользователя к той секунде. Клиент должен при отправке запомнить, сколько у него было очков и при получении ответа сравнить его с тем, что получил от сервера. Если есть расхождение то разница прибавляется к текущему количеству очков.

Т.е. вся логика на клиенте, но она продублированна и проверяется на сервере (например, проверка, что нет 10^20 кликов за секунду, что очков хватало на покупку апгрейда).

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

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

Если же вы хотите какую-то формулу или логику спрятать исключительно на сервере, то без задержек тут ничего не сделать.

В общем случае решения может и не быть вообще. Если формула - нетривиальный полином 20-ой степени, то решения символьного вообще не существует.

Системы символьной алгебры грубо говоря умеют кучу частных случаев. Типа туда забита формула решения линейных и квадратных уравнений.

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

И меня не устраивает "единственный" проблемный отрывок кода:
if ndata[i] % 2 != 0 and nf % 2 != 0: lucky += 1

Там вообще какой-то бред написан. При чем тут проверка на четность вообще?!

Вам надо подсчитать солько чисел из trda есть в ndata и вывести Lucky, если насчитали хотя бы 3 (перечитайте же условие задачи).

Соответственно должно быть что-то вроде

if nf == ndata[s]: cnt+=1
...
if cnt >=3:  print('Lucky')
    else: print('Unlucky')

Еще у вас вложенные циклы по одной и той же переменной i, может в питоне так и можно, но это обычно очень плохая идея.