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, заново прогоняя ДП.

В моей нотации С(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)

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

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

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

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

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

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

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

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

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

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

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

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

Во-первых, для таких больших коэффициентов вы в long long не влезаете, если в лоб считать.

Можно проверить в 2 этапа. Подсчитать A=a*x+b, B=c*x+d. Потом проверить что A*x*x = -B. Но тут нужно заранее отсечь случаи, когда abs(A) > abs(B)/(x*x). Тогда переполнений не будет.

Во-вторых, как же сложно у вас разбор случаев идет. Я не могу разобраться, что там происходит. Там наверняка опечатка, но я даже читать не хочу. Перепишите, пожалуйста. Вам надо найти самый старший ненулевой коэффициент и перебирать его делители. Плюс добавить корень 0, если этот коэффициент не d. Это делается сильно проще так:

if (d != 0) {
  n = d;
} else {
  s.push_back(0);
  if (c != 0) {
    n = c;
  } else if (b != 0) {
   n = b;
  } else {
   n = a;
  }
}
if (n == 0) {cout << "-1"; return}

Самое простое решение для понимания - полный перебор. Тупо 3 цикла - сколько монет с номиналом 2 взяли, сколько монет с номиналом 3 и сколько монет с номиналом 5. Каждый цикл от 0 до <Сколько осталось набрать> / номинал. Потом проверяем, что сумма сошлась. Более того, можно последний цикл пропустить и просто проверить, что оставшееся можно набрать пятаками.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}

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

Самое быстрое решение - динамическое программирование.

F(n,k) - можно ли набрать число n первыми k типами монет.

F(0.0) = 1
F(*, 0) = 0
F(n,k) = Sum(i = 0..have[k]) F(n-i*value[k], k-1)

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

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

Тут надо построить конечный автомат, который принимает строки, которые кончаются на заданную строку. Посмотрите эту статью, там в начале расписан этот автомат (секции перфикс функция - атомат КМП).

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

Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины n пройдет через конечное состояние ровно один раз. Для этого подсчитайте 2 вероятности: что путь из начала длины k дойдет до конечного состояния один раз, и что путь из конечного состояния длины n-k не вернется в него.

Обе эти вероятности можно подсчитать динамическим программированием:
P1(i, k) - вероятность того, что путь начиная с состояния i (i < n) за k шагов дойдет до состояния n первый раз. Это просто сумма по всем возможным переходам:

P1(i, k) = sum_{c - все символы} P1(next(i, c), k-1) * p(c)

База:

P1(m, 0) = 1
P1(m, k>0) = 0
P1(i < m, 0) = 0

Вторая вероятность: сделать k шаговиз состояния i и ни разу не войти в конечное состояние:

P2(i, k) = sum_{c - все символы, next(i,c) < m} P2(next(i, c), k-1) * p(c)

База:
P1(i, 0) = 1

Ответ к задаче - сумма по всем возможным длинам первой части пути:
sum_{k=m..n} P1(0, k) * P2(m, n-k)

Это решение через динамическое программирование будет O(n*m) по вермени и по памяти.

Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.

Вам просто надо пересечь 3 окружности на плоскости. По "формула пересечения окружностей" гуглится, например, это или это.

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

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

Составьте 6 уравнений сторон шестиугольника в виде Ax+By+C=0, так что C положительно (если нет - домножте на -1). Подставьте в эти 6 уравнений координаты точки, все они должны дать положительные значения (или нули, если точка на границе считается лежащей внутри в вашей задаче).

Почему это работает? Мы просто проверяем, что точка лежит с той же стороны от всех 6 прямых, что и центр (0, 0).

Как составить уравнения? Найдите координаты 6-ти углов. Если сторона = a, то координаты точек (a, 0), (a/2, sqrt(3)*a/2), (-a/2, sqrt(3)*a/2), (-a, 0) ...

Для уравнения одной из сторон возьмите в виде A разность по у у соседних точек, а в виде B разность по x (но с другим знаком). Потом подставьте туда координаты одной из точек и возьмите C так, чтобы был 0.

Можно все 6 уравнений составить на бумажке и закодировать в программе.

Пример для первой стороны:
A = sqrt(3)*a/2-0 = sqrt(3)*a/2
B = a - a/2 = a/2
C = -A*a - B*0 = -sqrt(3)*a*a/2.

Поскольку C отрицательно, меняем знаки:
A = -sqrt(3)*a/2
B = -a/2
C = sqrt(3)*a*a/2

Для второй прямой будет 0*x-a*y+sqrt(3)*a*a/2 = 0

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

Y у вас из множества R^W*H*2. Т.е. Y состоит из W*H*2 чисел проиндексированных тремя индексами - первый до w, второй до h, третий до 2. Соответственно в формуле считается сумма по всем значениям первых двух индексов. Y_wh - это пара чисел. У вас множества в примере неправильно составлены - там вместо a и b должны быть пары чисел.

Далее, нижний индекс 2 после || - это обозначение нормы L2 в двумерном пространстве - это корень второй степени из суммы квадратов (обычное декартово расстояние). Верхний индекс после || - это просто возведение в квадрат, который отменяет извлечение корня для ||...||_2.

Т.е. Вся эта формула говорит взять W*H*2 покомпонентные разности, возвести их в квадрат и сложить.

Количество сочетаний из 125 по 50. Или 125!/50!/75!
Потому что он обязательно сделает 50 шагов вправо и 75 шагов вверх. В любом порядке. Т.е. всего 125 шагов из которых любые 50 - по горизонтали.

Тут нет никакого алгоритма. Надо тупо записать формулу с математического языка, на вашем ЯП.

Вещественные числа в Си, например - это тип float. Корень - sqrt(). Пи - M_PI. В формуле есть e в степени чего-то там. Почти в любом языке уже есть функция exp().

Все решение - читаете 2 числа, потом присваивайте вещественной переменной один, деленное на второе число, помноженное на sqrt() от двух, умноженного на Пи. Это все умноженное на exp() от первой переменной, домноженной на себя, поделенной на 2 и на вторую переменную в квадрате.

Для двух переменных задача решается через расширенный алгоритм Евклида.

Решайте итеративно, добавляя новые переменные. Вот вы получили первые k переменных так что их сумма с коэффициентами равна GCD() коэффициентов. Пусть этот gcd(a1,a2,... ak) = d. Теперь решите тем же алгоритмом уравнение d*x + a(k+1)y = gcd(d,a(k+1)). y будет искомым значением последней переменной, а все предыдущие значения надо домножить на значение x.

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

Да, тут еще спецэффект есть, что с отрицательными числами не работает GCD. Надо поменять знаки у коэффициентов, запомнить это и в конце поменять знаки у переменных назад.

Решение за O(n log M), где n - количество переменных, M - максимальное значение коэффициентов.