Wataru

Пока вижу проблему, которая 100% приведет к тайм-лимиту. Вы при изменении приоритета ищите по всей очереди. Если вам дадут 500000 добавлений в очередь, а потом 500000 уменьшений случаного элемента, то ждать вы завершения программы будете очень долго.

Надо поддерживать массив позиций по по всем айдишникам. При любом перемещении пары элементов в массиве в очереди надо обновлять этот массив позиций.

При изменении приоретета уже не надо никакого find, потому что позиция уже будет доступна в массиве.

При добавлении нового элемента не надо вызывать build_heap. достаточно только shift_up от нового элемента. У вас в программе отдельно этой функции нет, но она фактически реализована в decrease_key. Только нужно, опять же, проходится не по всей очереди, а только по отцам. В цикле надо делать не i--, а i = (i+1)/2-1.

И ошибка как раз в decrease_key, У вас цикл по i, а внутри все время используется k.

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

По коду есть комментарии:
1)

if ((valVAT == 10) || (valVAT == 18) || (valVAT == 20)) {
...

Тут у вас один большой мега-if в котором что-то делается. Гораздо проще для понимания и визуально читабельнее, если делать "ранний выход". Вместо if(a) { много кода } стоит писать:

if (!a) {
  continue; // или return; если это в функции.
}
// много кода.

У вас стоит сначала проверить, что valVAT == 0 и выйти из цикла через break в этом случае. Потом проверить, что valVat != 10 && valVAT != 18 && valVAT != 20 и вывести сообщение об ошибке и сделать continue. Дальше уже идет тело цикла с вычислениями.

2) Вместо if(chng == 1) {} else if (chng == 2) {}... стоит использовать конструкцию

switch (chng) {
case 0:
  // код
  break;
case 1:
  // код
  break;
case 2:
  // код
  break;
default:
  // сообщение об ошибке
  continue;
}

3)
sleep(1) после вывода сообщения об ошибке, на мой взгляд не нужен. Зачем это? Заставить пользователя прочитать сообщение об ошибке?

Вы не копируете '\0' на конце. Поэтому после приписывания идет мусор. И так получается, что у вас в памяти там мусор "v\0".

Вторая проблема, вы пишите в строку s, не меняя ее размер.
char s[] = "abc"; выделяет ровно столько памяти, сколько нужно для "abc", да еще и на стеке, раз у вас переменные локальные.

Вы при дописывании чего-то к строке затираете другие переменные. Так у вас совпало, что после name идет surname на стеке. Поэтому вы переписываете память второй строки (но без первого символа, который занял место '\0' в name. Именно поэтому мусор в конце - это неперезаписанный конец surname "v\0". Если поменять местами переменные, то вы может стек перепишите и у вас программа вообще упадет.

Вам надо строки выделять с запасом: char name[1000] = "Ivan";

Пусть координаты x0,y0. Расстояние можно считать по этой формуле (вики).

Вам придется или скопировать код по ссылке и переписать на питоне, или использовать этот пакет.

Дальше, вам надо начиться отступать от заданной точки на север или восток на 1 метр. Это можно или медетировать над формулой выше а можно просто запустить бинарный поиск, который будет искать изменение широты или долготы. Пусть d - сколько вам надо отложить в метрах, R - радиус земли в метрах. Тогда ищите изменение на отрезке (0, 4*r*180/(2*Pi*R)). Пробуйте откладывать текущее значение по широте или долготе, считайте расстояние по формуле и, если оно больше d, заменяйте верхнюю границу отрезка на середину, иначе заменяйте нижнюю границу. Остановите бин.поиск, когда отрезок станет достаточно мелким (например <1e-10).

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

Сначала сгенерируйте точки на одной вертикале с начальной. Для этого повторно откладывайте 1м на север и юг от нее, пока расстояние до (x0,y0) не превысит ваш радиус. Бинпоиск достаточно запустить ровно один раз в самом начале и дальше именно это приращение откладывайте вверх и вниз.

Потом аналогичным образом откладывайте от каждой сгенеренной точки новые точки на запад и восток. Сначала для каждой точки бинпоиском найдите нужное приращение по долготе. Потом откладывайте его влево и вправо, пока не выйдите за радиус от (x0,y0).

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

Допустим, 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 ближайших соседей, например.

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