М.Двач / Программирование

Этого треда уже нет.
Это копия, сохраненная 31 июля 2023 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

288 Кб, 745x750
Сап, двач. Сможешь решить задачу хотя бы за O(N^2)? Есть лотерея, устроенная следующим образом: В не 20 июня, 22:37 2739903 В конец треда | Веб

Сап, двач. Сможешь решить задачу хотя бы за O(N^2)?
Есть лотерея, устроенная следующим образом:
В ней N участников и N призовых мест, причем награда за первое место больше или равна награде за второе и т.д.
У каждого участника Ai лотерейных билетов.
Розыгрыш проходит так:
1. Из лохотрона достают номер билета, который занимает первое место.
2. Из лохотрона изымают номера билетов, которые были у игрока, только что получившего приз.
3. возвращаемся к п.1.
Исходя из структуры выплат и количества билетов у каждого участника, нужно вычислить стоимость всех Ai билетов каждого игрока.

Ответы399174254743191

2 20 июня, 22:58 2 2739917

>>2739903 (OP)
Лучшее, что пришло мне в голову - это получить все N! перестановок Ai, затем вычислить вероятность каждой такой перстановки и умножить эту вероятность на соответствующие выплаты. А потом просто все сложить. Но тогда временная сложность будет O(N*N!) а это как-то медленно.

3 21 июня, 00:50 3 2740016

Я лучше аниме посмотрю.

4 21 июня, 16:51 4 2740674

бамп

5 21 июня, 20:04 5 2740863

бамп

sage 6 21 июня, 20:17 6 2740882

Сажи

Ответы40891

7 21 июня, 20:19 7 2740891

>>2740882
За что?

# OP 8 21 июня, 21:57 8 2740987

бамп

# OP 9 22 июня, 06:06 9 2741095

бамп

10 23 июня, 12:42 10 2742522

бамп

11 23 июня, 12:59 11 2742547

>>2739903 (OP)
Решения:
Стоимость билета = [Сумма выигрышей(N вычислений) + профит организаторов лотереи]/ N * Ai.
Сложность O(N).

Ответы431724317843181

12 23 июня, 23:57 12 2743172

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

13 24 июня, 00:02 13 2743178

>>2742547
И да, вопрос не в стоимости одного билета, а в стоимости ВСЕХ билетов у каждого участника, ведь чем больше у участника билетов, тем дешевле каждый его билет по отдельности. Мы не можем купить несколько билетов у кого-то из игроков, мы должны покупать все. Суть в том, как посчитать математическое ожидание. А точнее - вероятность занять каждым игроком каждое призовое место.

14 24 июня, 00:03 14 2743181

>>2742547

15 24 июня, 00:14 15 2743191

>>2739903 (OP)
1) В барабане, из которого извлекают номера выигрышных билетов, есть повторяющиеся номера?
2) Для любого ли номера, имеющегося в барабане, верно, что существует участник с билетом, имеющим этот номер? Если ответ на этот вопрос нет, то есть ли какое-то ограничение на количество номеров, лежащих в барабане?
3) Верно ли, что у всех лотерейных билетов различные номера?
4) Формализуй, что понимается под стоимостью билета.

Ответы43196

16 24 июня, 00:44 16 2743196

>>2743191
1) нет
2) каждому билету соответствует ровно один номер в барабане
3) верно
4) стоимости одного билета нет. В этой задаче речь идет о стоимости всех билетов каждого игрока. За сколько денег ты готов купить все билеты у кого-то из игроков? Понятно, что чем больше билетов ты покупаешь - тем больше денег можешь себе позволить заплатить.

Ответы43201

193x21
sage 17 24 июня, 00:49 17 2743197

Я приведу пример:
У трех игроков 3, 2, 1 билетов соответственно.
За первое место платят 3 йобы, за второе - 2 йобы, за третье 1 йобу.
В таком случае, три билета первого игрока стоят 2,35 йобы,два билета второго игрока стоят 2,066666667 йобы, один билет третьего игрока стоит 1,583333333 йобы.
Задача нихуя не тривиальная.

Ответы432114367743722

18 24 июня, 00:54 18 2743201

>>2743196
> каждому билету соответствует ровно один номер в барабане
И все билеты распроданы тем самым N участникам? Ну то есть не бывает такого, что номер в барабане нет, но билет с этим номером не принадлежит никому из рассматриваемых N участников?

Ответы4320343238

19 24 июня, 00:55 19 2743203

>>2743201
> номер в барабане нет
тут должно быть "номер в барабане есть"

20 24 июня, 01:19 20 2743211

>>2743197
Короче, ты просто математические ожидания выигрышей вычисляешь?

Ответы43239

193x21
21 24 июня, 04:31 21 2743238

>>2743201
Ну да, сколько билетов, столько и номеров.

22 24 июня, 04:32 22 2743239

>>2743211
Да

Ответы43241

23 24 июня, 05:05 23 2743241

>>2743239
Короче, пока хз, челикс. Какая-то нетривильная задачка. У меня для тебя есть странная идея - можешь попробовать поискать на codeforces задачи на вычисление математических ожиданий. Возможно там найдётся задача с похожей структурой.

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

# OP 24 24 июня, 16:50 24 2743518

Спасибо, бро, попробую поискать.
А насчет Монте-Карло - я пробовал, для N=10 погрешность 2%, что не есть гуд.

25 24 июня, 21:32 25 2743677

>>2743197
Т.е. i-й игрок получает N йоб за Ai билетов? Че тут считать то тогда?
Если мы нумеруем игроков от 1 выигравшего, то стоимость одного i-го билета = (N + 1 - i) / Ai
Сумма всех билетов это сумма арифметической прогрессии (1 + N) * N /2
че еще считать? яннп

Ответы43682

26 24 июня, 21:41 26 2743682

>>2743677
Чел, ты знаешь что такое математическое ожидание?

Ответы43685

27 24 июня, 21:46 27 2743685

>>2743682
Да, я выпускник математического факультета. Где в условии написано про мат ожидание? Условие задачи поставлено максимально мутно, нигде не сказано что нужно перебрать всех участников и все комбинации выигрышей. А здесь вообще написано "три билета первого игрока стоят 2,35" но "первый игрок выиграл 3 йобы за 3 билета" что вообще выглядит как полная шиза. Поэтому мой ответ это тупо троллинг. И да когда мне на собесах что-то такое спрашивали, я просто нахуй посылал.

Ответы43698

28 24 июня, 21:54 28 2743698

>>2743685
Да, в условии задачи написана хуйня. Но если ты почитаешь сам тред, то условие там конкретизировалось. В частности, было указано, что нужно считать мат. ожидание.

> И да когда мне на собесах что-то такое спрашивали, я просто нахуй посылал.
При чём тут твои собесы.

//не ОП, если что

зы
> Да, я выпускник математического факультета.
Какого именно?
Бак, мага или кандидат?
По какой тебе зазищал дисер/диплом?

Ответы4370343705

29 24 июня, 21:58 29 2743703

>>2743698
Специалист блет, по теме поиска путей в автомобильном трафике 2001 г

Ответы43706

30 24 июня, 21:58 30 2743705

>>2743698
"... теме защищал ..."

31 24 июня, 22:00 31 2743706

>>2743703
> по теме поиска путей в автомобильном трафике
Понятно, то есть к математике отношения не имеешь. Это точно математический факультет был, а не зашкваренная прикладная математика? А то тема уж больно на второе намекает.

Ответы43709

32 24 июня, 22:03 32 2743709

>>2743706
Там суть была в том что под это система писалась на смолтоке. Факультет да, так и назывался, математический.
Собесы при том что эта тема выглядит как обиженка пришла с собеседования с этой задачей и вместо того, чтобы честно раскинуть мозгами, решила самоутвердиться потролив анона

Ответы43713

33 24 июня, 22:08 33 2743713

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

34 24 июня, 22:33 34 2743722

Так, ладно, начнем с этого >>2743197, это референсное решение?

Ответы43737

35 24 июня, 23:03 35 2743737

>>2743722
> это референсное решение
Не знаю, что ты под этим подразумеваешь, но этот пример привёл оп, поэтому ответы, данные в этом сообщении можно считать правильными.

36 25 июня, 00:36 36 2743767

Так я "решил" но пока N!

37 25 июня, 04:03 37 2743786

В принципе понятно как за 2 ^ N -1 решить

38 25 июня, 05:14 38 2743790

Суть такова, N-ю сумму заработают N игроков, независимо от их билетов, разницу между N-й и N-1 заработают N-1 игроков с вероятностью = сумма их весов и т.д, 1-й игрок заработает последнюю разницу со своим весом. Но ето перебор сочетаний ои 1 до N из N

Тред утонул или удален.
Это копия, сохраненная 31 июля 2023 года.

Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее

Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.

« /pr/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion