Wataru

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

Допустим, 19 = 2+2+5+5+5. Но можно же переставлять карты местами. Ведь диллеру могли прийти 5, потом вторая 5, потом 2, потом 2, потом 5. Да и сами пятерки могли прийти 3! способами. Однако, вы не можете поставить 2 последней, потому что сумма четырех первых карт уже 17. Диллер бы не тянул эту последнюю двойку.

Но 19=3+3+4+4+5 уже можно выбрать всеми 5! разными способами. Поэтому эти 2 комбинации, хоть и дают одну и ту же сумму и содержат одинаковое количество карт, можно получить с разной вероятностью.

Правильное решение с применением динамического программирования:

Во-первых, переберите, какая карта будет вытянута последней. Найдите вероятности всех сумм с учетом этой карты (так, что она переваливает сумму за 17, но не пердыдущая). Потом просуммируйте по всем таким картам.

Исключите эту последнюю карту из колоды. Теперь надо найти сколько наборов карт заданной длины дают каждую сумму < 17. При этом при подсчете вероятности можно переставлять все эти карты как угодно. Поэтому имеет значение, сколько карт мы использовали для суммы.

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

При подсчете у вас есть 2 варианта - последняя из k карт или входит, или нет в сумму (допустим массив a[] хранит веса карт).
Т.е. F(n,k,s) = F(n,k-1,s)+F(n-1,k-1,s-a[k]).

База:
F(0, k, s) = 1 если s==0; 0 иначе
F(n,0,s) = 1 если n==0 и s==0; 0 иначе.
F(n, k, s<0) = 0

Можно сэкономить на памяти и считать в двумерном массиве с конца в начало, выкинув k (второй параметр).

Потом искомая вероятность набрать сумму x c последней картой l, если осталось в колоде max_k карт (если x<17+l, x>=17, иначе - вероятность 0):

P(x) = sum_{n=1..max_k} f(n, max_k, x-l) * n! * (max_k-n)! / (max_k+1)!

Тут перебор по всем возможным количествам карт у диллера. Дальше берем количество способов набрать нужную сумму из ДП. Потом домножаем на n!, потому что эти карты в руке у диллера могли прийти в любом порядке. Дальше домножаем на вероятность вытянуть конкретные n+1 карт (считая последнюю) из колоды с max_k+1 картами. Это 1/(max_k+1)/max_k/,,,/(max_k-n+1) = (max_k-n)!/(max_k+1)!

Этот множитель после f() можно пересчитывать за одно домножение и деление
при увеличении n.

Напоминаю, это надо просуммировать по всем возможным картам взятым за l, заново прогоняя ДП.

В этой задаче все должно в long long помещаться. Никаких трюков не надо.

У вас ошибка вот тут:
long long div_up(int x, int y)

Типа параметров - int. Вы когда в эту функцию передаете long long сумму - происходит переполнение.

Просто измените типы на long long и должно пройти.

head, tail и next тут - это ссылки не элементы в списке, указатели или как это в typescript называется. Эти переменные не хранят LinkedListNode, а лишь указывают на такой элемент где-то в памяти. Первая операция this.tail.next = newNode; делает последний элемент в списке ссылающимся на новый элемент, который мы добавляем в конец. Просто обновляя ссылку у последнего элемента.
Следующая операция передвигает ссылку tail указывать на новый, только что добавленный, элемент.

В самом начале, когда вы будете добавлять второй элемент head и tail будут указывать на одну и ту же вершину. Поэтому изменение tail.next одновременно меняет и head.next, потому что head и tail - указывают в одно и то же место.

Потому что иначе невозможна рекурсия. Что если у вас f(1,3) захочет вызвать f(0,0). Еще придется эти глобальные переменные переписать и потом как-то восстанавливать, если после вызова f(1,3) еще что-то хочет делать с этими параметрами.

Потом, это тупо неудобно. Для каждой функции нужен свой набор глобальных переменных.

Это про второй ваш вариант.
В третьем же a и b локальные переменные. Получается вы их никак снаружи функции не сможете задать.

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

У вас какая-то странная схема в 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 равные по площади куска пятиугольника.

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