Wataru

Сила трения. Имеет разрыв в v=0. Ездили когда-нибудь в автобусе или метро каком-нибудь? Пробовали не держаться за поручни? Вот когда оно тормозит, вас вперед тянет некая сила, которая внезапно обрывается, когда транспорт полностью останавливается. Вот это оно фактически. Сила трения действует на транспорт, вам, с вашей точки зрения, кажется, что это вас тянет вперед (хотя это корпус автобуса тянет назад). Но в момент достижения нулевой скорости эта сила трения становится резко равной нулю.

Соберите вашу функцию из квдаратичных или кубических сплайнов.

Когда подберете параметры, функция будет вычислятся кусочно. Сначала найдите к какому отрезку относится текущее время (или тупо циклом или набором if-else, или, если сделаете отрезки одинаковым количеством часов, то можно поделить время на длину отрезка и округлить вниз, чтобы получить номер отрезка). Потом вычислите значение нужного сплайна, что будет просто вычислением полинома второй или третьей степени.

Ну, или можете просто задать нексолько ключевых значений, и проинтерполировать полиномом лагранжа. Правда тут сложно будет заставить его идти именно как вам хочется. Через точки-то он точно пройдет, но вот между ними может иметь какие-то левые пики и изгибы. Так что придется поэксперементировать. Можно поиграться, например, в wolframalpha.com (введите "interpolating polynomial calculator", потом задайте значения функции в точках и получите и график и формулу. Ссылку дать не могу, qna ссылки на wolfram банит за одно со спамерскими ссылками по ошибке).

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

Допустим, 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 пройдет через конечное состояние ровно один раз. Для этого подсчитайте 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) по вермени и по памяти.

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