Wataru

У вас какая-то странная схема в partition.

Представьте, что у вас массив из 2 элементов и первый - больше второго (a[0] = pivot > a[1]).

До цикла l = 0, h = 2, i = 0. Потом в первом while вы делаете i++. Потом сравниваете a[i] с pivot в первом while. a[1] < pivot по предположению, поэтому вы делаете i = 2. Все - вы уже вышли за границу массива.

Перепишите со стандартной схемой разбиения Хоара или Ломуто.

Или придется всякие условия i < j везде дописывать, но я не уверен.

Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.

Это называется топологическая сортировка. Реализуется обычно одним поиском в глубину. Есть статья на хабре.

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

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

В моей нотации С(n,k) - сочетания из n по k.

Нужно знать вот это тождество для сочетаний:
С(n,k) = C(n,n-k).

Применив к тому, что у нас под знаком суммы:
C(2n+1, 2k) = С(2n+1, 2n+1-2k)

Когда k проходит от 0 до n, слева получаются сочентания по всем четным числам от 0 до 2n+1, а справа - по всем нечетным.

Есть формула, что сумма всех сочетаний из n по всем возможным k будет 2^n, Получается тупо из раскрытия (1+1)^n по биному Ньютона.

Но у нас тут не сумма по всем, а только по четным. Но выше мы уже видели, что суммы по всем четным и всем нечетным совпадают. Отсюда напрашивается варинат просто подсчитать удвоенную искомую сумму.

Формально: пусть X - искомая сумма в задаче.
тогда
X+X = sum_{k=0..n} C(2n+1, 2k) + sum_{k=0..n}(2n+1, 2n+1-2k) =
= sum_{k=0..n} C(2n+1, 2k) + sum_{k=0..n}(2n+1, 2*(n-k)+1) =
= sum_{k=0..n} C(2n+1, 2k) + sum_{k=n..0}(2n+1, 2*(n-k)+1) =

Во второй сумме заменим n-k=j. Т.к. k=n..0, то j = 0..n.

= sum_{k=0..n} C(2n+1, 2k) + sum_{j=0..n}(2n+1, 2*j+1).

А это тупо сумма по всем возможным k от 0 до 2n+1 (только четные и нечетные в отдельных суммах):
= sum_{k=0..2n+1} C(2n+1, k) = 2^(2n+1)

Остюда X = 2^(2n+1) / 2 = 2^(2n)

Вроде все правильно. Какие ограничения? Может быть переполнение, ведь максимальный ответ n(n-1)/2. Для переполнения int достаточно 65536 чисел в массиве.

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

Варианты метрик:

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

Некоторые метрики имеют смысл только при фиксированном количестве кластеров, как первая.

Разные метрики дают разные кластеризации и все они в каком-то смысле хорошие. Что именно подходит вам в вашей задаче - можете судить только вы эмпирически.

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

Многие метрики, если они аддитивны как первая, можно считать динамическим программированием: f(i,k) - значение метрики если мы разбили первые i точек на k кластеров.

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

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

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

Это сложная задача - тут нет простого и быстрого алгоритма.

Можно свести ее к integer linear programming и решать какой-то из множества существующих библиотек/солверов. Если числа маленькие, то можно или полный перебор или какую-то динамику, типа решения задачи о рюкзаке сделать (тут надо будет набранные суммы во всех приборах взять в параметры).

Если нужно не обязательно оптимальное решение - а что-то не слишком ужасное, то можно делать жадность, как Adamos предложил.

У вас переменные correct_Login и correct_Password не инициализируются. Вы их можете затереть в 0, но 1 они никогда не были и не станут.

Теперь несколько замечаний по коду.

Не нужно декларировать extern в коде функции для глобальных переменных. Не нужно дописывать '\0' на конце строковых констант, оно там и так будет в конце добавлено автоматически.

Возьмите центр вписанной (и описанной) окружности. Разделите каждую сторону на 3 равные части. Проведите отрезки из центра во все 5 вершин и 10 точек на сторонах. Вы получите 15 треугольников, с одинаковыми внешними сторонами (1/3 стороны пятиугольника). Еще у всех этих треугольников одинаковые высоты (радиус вписанной окружности). Поэтому они все одинаковой площади. Теперь разбейте их на 3 группы по 5 подряд идущих треугольников - вот и ваши 3 равные по площади куска пятиугольника.

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

При копировании назад из временного массива b в массив a у вас индексация с ошибкой. Хоть b индексируется с 0, вы обращаетесь к элементам начиная с s.

unordered_map может работать за линию в худшем случае. Это если происходит много коллизий. Стандартная реализация еще и дико медленная, через связные списки работает и часто использует тривиальные хеши (буквально, значение int берется за значение хеша). Подобрать смертельный тест для такого хэша совсем не сложно. Введите вашей программе на вход координаты деревьев i*8192 - если я правильно понимаю, unordered_map будет работать ооочень долго.

Можно избавиться от таких тривиальных коллизий, если реализовать свою хеш функцию. А там можно хоть (x * 239017l) % (1<<31) возвращать. И то, лучше будет.

Еще, чтобы избавиться от постоянных рехешированний можно добавить вот это:

len.reserve(1048576);
len.max_load_factor(0.25);

Говорят, что если заранее зарезервировать место и указать load_factor поменьше, то unordered_map будет раз в 10 быстрее.

Плюс, константа у unorderd_map выше - ибо надо хеши считать и перехешировать всю таблицу, если чисел становится много. Может, оно бы было быстрее для миллиона чисел, а не 100000, как у вас там.

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

Потому что компилятор ищет Python.h во время компиляции. В это время никакой main() не выполняется и chdir ничего не делает. Надо указать компилятору, где искать хедеры.

Как вы компилируете? Вы под виндовс, видимо, сидите - у вас visual studio или вы gcc используете? Или что-то еще? Используете ли вы cmake или какую-то еще систему сборки? Приведите буквально ту команду/ваши действия, которые приводят к выводу на экран ошибки.

В итоге все должно вылиться в дописывание флага -I"c:\Python39\include" к команде компиляции. Если какая-то система сборки, то прямо в файле проекта можно как-то указать эту опцию.

Сам же include нужно делать без всяких путей, просто #include <Python.h>.