Wataru

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

Можно в тестах требовать совпадение с некоторой абсолютной или относительной погрешностью.

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

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

Возможно там переполнение. Убедитесь, что у вас все хеши везде считаются только с участием unsigned типов. Переполнение в signed - это Undefined behavior.

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

Странное задание. Какая польза от этого сокращения сравнений, если всего в результате вставки переместится до O(log n) элементов?

Но, если так надо, то вам нужно для каждого числа сначала узнать номер старшего ненулевого бита (most significat bit - MSB), и потом сдвинуть верхнее число вправо на половину разницы в позициях старших битов.

1 = 0000001b, msb = 0
18 = 0010010b, msb = 4

Разность - 4 разряда. Значит, надо сдвигать на 2 разряда вправо:
18 >> 2= 0010010b >> 2 = 00100b = 4

Еще пример: для 4 и 18 msb были бы 2 и 4, разность -2. Сдвинув 18 на 2/2=1 разряд вправо, вы бы получили 9.

Чтобы эта оптимизация давала хоть какую-то пользу, надо находить msb очень быстро. Или предподсчитайте их для всех возможных индексов, или надейтесь, что в вашем языке есть встроенная функция, которая вызывает нужную инструкцию процессора, типа __builtin_clz.

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

Для предподсчета просто в цикле задавайте msb[i] = msb[i/2] + 1;

TL;DR:

S = Pi*sqrt(3 / [ (1/L1+1/L2+1/L3)^2-2*(1/L1^2+1/L2^2+1/L3^2) ])

тут L1, L2, L3 - квадраты трех измерений.

Вывод формул:
Чуть-чуть аналитической геометрии и куча элементарной алгебры помогут вам вывести эти уравнения.
Если ввести систему координат с осями по главным радиусам эллипса, то уравнение эллипса будет:
x^2/a^2+y^2/b^2 = 1

При этом все точки под углом alpha к большой полуоси будут на луче:

x(t, alpha) = t*cos(alpha)
y(t, alpha) = t*sin(alpha)

Обозначим синус и косинус угла для первого измерения как:
s = sin(a1), c = cos(a1)

Пусть квадраты расстояний - L1, L2, L3.

Если пересечь луч и эллипс, то можно составить уравнение для длины вдоль угла a1 (первое измерение), просто подставив известные x(a1, sqrt(L1)) и y(a1, sqrt(L1)).
1/L1 = c^2/a^2+s^2/b^2

Для остальных измерений надо прибавлять 120 градусов к углу под cos и sin. Если раскрыть cos(120+a1) = cos(120)cos(a1)-sin(120)sin(a1) и sin(120+a1) = cos(120)sin(a1)+sin(120)cos(a1), то можно составить еще 2 уравнения:

1/L2 = (-1/2*c-sqrt(3)/2*s)^2/a^2+(sqrt(3)/2*c-1/2*s)^2/b^2
L3 = (-1/2*c+sqrt(3)/2*s)^2/a^2+(-sqrt(3)/2*c-1/2*s)^2/b^2

Всего с учетом тригонометрического тождества s^2+c^2=1 у нас 4 уравнения на 4 неизвестных a, b, c, s.

Но нам не нужны все значения. Площадь эллипса Pi*a*b, а радиусы эллипса - a и b.

Раскрыв квадраты выше и всячески складывая эти уравнения можно получить в итоге

1/a^2+1/b^2 = 2/3*(1/L1+1/L2+1/L3)
1/a^2*b^2 = [ (1/L1+1/L2+1/L3)^2-2*(1/L1^2+1/L2^2+1/L3^2) ]/3

Отсюда площадь:

S = Pi*ab = Pi*sqrt([ (L1+L2+L3)^2-2*(L1^2+L2^2+L3^2 ]/3)

Чтобы найти радиусы эллипса, вам надо найти a и b. Выше уже даны два уравнения для суммы и произведения 1/a^2 и 1/b^2 - можно из них получить квадратное уравнение для t=1/a^2. Два его решения и будут вашими радиусами эллипса (не забудьте взять корни и обратить). Тут надо аккуратно подставить выражения в школьные формулы для квадратного уравнения.

Нет, тут O(n^2). С чего вы там взяли log?

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

Обрабатывайте все записи в хронологическом порядке.

При приходе in, вы добавляете в стек (через append у list-а) пару (цена, количество).

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

Что-то вроде такого (сам не питонист, возможно придется переписать немного)

def getOstatokLIFO(df):
  stack = [];
  for index, row in df.iterrows():
    if row.operation == "in":
      stack.append([row.price, row.quantity])
      continue
    left = row.quantity
    while left > 0:
      if left >= stack[-1][1]:
        left -= stack[-1][1]
        stack.pop()
      else:
        stack[-1][1] -= left
        left = 0
        
  return stack

Но вообще, DataFrame очень медленно работет при такой последовательной обработке, поэтому я бы посоветовал вам не создавать pandas dataframe изначально, и получить ваши данные в виде списка словарей, touples или объектов. А алгоритм расчета предполагает последовательную обработку.

Точно также, как ищите наидлиннейший путь. Будет у вас DFS, который возвращает количество путей из заданной вершины до конечной, с заданными уже посещенными вершинами. В нем перебираете все исходящие ребра, запускаетесь рекурсивно (если конец ребра не посещен уже) и суммируете все результаты. Если пришли в конечную вершину - то возвращаете 1 (1 путь длины 0 - уже пришли). В начале функции помечайте вершину посещенной, чтобы в нее опять не входить. В конце функции помечайте вершину не посещенной, чтобы можно было другие пути через эту вершину считать. Разница с самым длинным путем в том, что вы тут суммируете результаты всех рекурсивных вызовов DFS, а не берете максимум. Ну и еще +1 не надо, как к длине, прибавлять.

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

(Полное условие есть в комментариях к вопросу)

Алгоритмически тут такое решение: Постройте граф из n вершин, где есть ребро между всеми парами вершин, которые можно менять местами. Подсчитайте размеры компонент связности и перемножте их факториалы. Так, если компонента всего одна, то ответ будет n! (все возможные перестановки из n чисел можно получить так).

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

Если нужно именно математическая формула от P, то тут все сложно, осбоенно, когда числа P достаточно большие. Например, M=6, P1=3 P2=4. Из вершин 3 и 4 вообще нет ребер, а ребро P2 есть только между крайними вершинам. Подобным образом можно создать весьма сложные структуры.

Однако, если все P меньше равны половины N, то есть простой ответ. В графе будет GCD(P1+1,...,PM+1) компонент связности - все вершины, дающие один и тот же остаток от деления на наибольший общий делитель P+1. И ответ будет что-то вроде (floor(N/G)!)^G*(floor(N/G)+1)^(N%G) (где G - этот самый наибольший общий делитель всех P, увеличенных на 1).

Это потому, что при достаточно маленьких P, всегда можно отложить их в одну или другую сторону и так в итоге сделать шаг длинной G.

Доказательство примерно такое: Рассмотрим первую половину вершин. Из них можно отложить вправо самое большое P. А потом влево любое из оставшихся P. Так мы фактически отложили от всех этих вершин любую разность двух P вправо. Если сначала отложить вправо меньшее P, а потом максимальное P назад, то мы отложили ту же разность влево. Из соображений симметричности получается, что мы можем отложить любую разность P от всех вершин в любую сторону. Все разности также меньше половины N. Продолжая этот процесс, как в алгоритме эвклида, мы получим, что можно от каждой вершины отложить G, а значит все вершины с одинаковым остатоком от деления на G принадлежат одной и той же компоненте связности.

Если какие-то P больше половины (аккуратно сами посмотрите, там +-1 где-то возможно нужно), то я не знаю формулу. Остается только писать DFS на графе.

Подобно задаче о 4-х шпинделях. Чтобы переместить самый большой диск на последний шпиндель, сначала надо все меньшие диски куда-то деть. Можно их парковать на 2-ом шпинделе или на 8-ом. Потом подвигать последний диск до 7-ого шпинделя, потом перепарковать часть с 8-ого на 6-ой и подвигать последний диск. Потом назад с 6-ого на 8-ой и оставшиеся со 2-ого на 8-ой. И надо перебрать все варианты - сколько дисков куда пихать.

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

Чтобы это работало быстро, надо делать мемоизацию и не считать функцию с одним и тем же набором параметров несколько раз.

Интересно, что ответ растет гораздо медленее, чем для 3-х шпинделей:

6
13
22
36
55
82
117
163
219
289
375
484
623
800
1024
1300
1651
2090
2643
3333

Есть целая наука об этом. "Временные ряды", вроде, называется. Там есть куча всяких моделей, типа ARIMA.

X AND (2^1+2^2) ИЛИ X AND 230

Слева же правильно написано, но вы как-то из 2+4 получили 230.

Х AND (255–2^2–2^7) ИЛИ Х AND 221

Тоже самое. Правильную операцию сделали, но както из 255-4-128 получили 221, хотя должно быть 123.
И вместо X пишите A или B в заданиях. Дальше такие же ошибки.

Гуглите "алгоритм генерации размещений". Находится, например, это.

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

Или можно сгенерировать размещения из {1,2,3,...N} а потом использовать эти числа в размещениях, как индексы символов. Надергайте из заданной строки символы по этим позициям и получите размещение из символов, а не чисел.

Ну, это известная формула - количество пар среди n объектов. Для самого левого подходит n-1 правых концов. Для второго - их будет n-2. Для последнего - 0. Сумма (n-1)+(n-2)+...+1+0 = (n-1)n/2. Можно через сумму арифметической прогрессии получить.

mergeSort(a, temp, 0, mid);

Надо сортировать часть с lo по mid. А не с 0.

Если обратная нотация, то знак ± должен, как и бинарные операции, идти после операндов. Тогда -(-1 + 2) становится 1 ± 2 + ±. По ± надо менять знак числа на верхушке стека.

Соответственно в парсере, если видите унарный минус перед скобками, то переводите скобки в нотацию, а потом дописываете ±.