Двач.hk прислал битые данные.
Вы видите копию треда, сохраненную 31 июля 2023 года.
Можете попробовать обновить страницу, чтобы увидеть актуальную версию.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Вы видите копию треда, сохраненную 31 июля 2023 года.
Можете попробовать обновить страницу, чтобы увидеть актуальную версию.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
288 Кб, 745x750Сап, двач. Сможешь решить задачу хотя бы за O(N^2)?
Есть лотерея, устроенная следующим образом:
В ней N участников и N призовых мест, причем награда за первое место больше или равна награде за второе и т.д.
У каждого участника Ai лотерейных билетов.
Розыгрыш проходит так:
1. Из лохотрона достают номер билета, который занимает первое место.
2. Из лохотрона изымают номера билетов, которые были у игрока, только что получившего приз.
3. возвращаемся к п.1.
Исходя из структуры выплат и количества билетов у каждого участника, нужно вычислить стоимость всех Ai билетов каждого игрока.
Есть лотерея, устроенная следующим образом:
В ней N участников и N призовых мест, причем награда за первое место больше или равна награде за второе и т.д.
У каждого участника Ai лотерейных билетов.
Розыгрыш проходит так:
1. Из лохотрона достают номер билета, который занимает первое место.
2. Из лохотрона изымают номера билетов, которые были у игрока, только что получившего приз.
3. возвращаемся к п.1.
Исходя из структуры выплат и количества билетов у каждого участника, нужно вычислить стоимость всех Ai билетов каждого игрока.
>>39903 (OP)
Лучшее, что пришло мне в голову - это получить все N! перестановок Ai, затем вычислить вероятность каждой такой перстановки и умножить эту вероятность на соответствующие выплаты. А потом просто все сложить. Но тогда временная сложность будет O(N*N!) а это как-то медленно.
Лучшее, что пришло мне в голову - это получить все N! перестановок Ai, затем вычислить вероятность каждой такой перстановки и умножить эту вероятность на соответствующие выплаты. А потом просто все сложить. Но тогда временная сложность будет O(N*N!) а это как-то медленно.
Я лучше аниме посмотрю.
бамп
бамп
>>40882
За что?
За что?
бамп
бамп
бамп
>>39903 (OP)
Решения:
Стоимость билета = [Сумма выигрышей(N вычислений) + профит организаторов лотереи]/ N * Ai.
Сложность O(N).
Решения:
Стоимость билета = [Сумма выигрышей(N вычислений) + профит организаторов лотереи]/ N * Ai.
Сложность O(N).
>>42547
Спасибо что откликнулся, но таких переменных здесь нет. На самом деле, задаче не про лотерею, а про покер, и каждый билет - это фишка.
Спасибо что откликнулся, но таких переменных здесь нет. На самом деле, задаче не про лотерею, а про покер, и каждый билет - это фишка.
>>42547
И да, вопрос не в стоимости одного билета, а в стоимости ВСЕХ билетов у каждого участника, ведь чем больше у участника билетов, тем дешевле каждый его билет по отдельности. Мы не можем купить несколько билетов у кого-то из игроков, мы должны покупать все. Суть в том, как посчитать математическое ожидание. А точнее - вероятность занять каждым игроком каждое призовое место.
И да, вопрос не в стоимости одного билета, а в стоимости ВСЕХ билетов у каждого участника, ведь чем больше у участника билетов, тем дешевле каждый его билет по отдельности. Мы не можем купить несколько билетов у кого-то из игроков, мы должны покупать все. Суть в том, как посчитать математическое ожидание. А точнее - вероятность занять каждым игроком каждое призовое место.
>>42547
И да, вопрос не в стоимости одного билета, а в стоимости ВСЕХ билетов у каждого участника, ведь чем больше у участника билетов, тем дешевле каждый его билет по отдельности. Мы не можем купить несколько билетов у кого-то из игроков, мы должны покупать все. Суть в том, как посчитать математическое ожидание. А точнее - вероятность занять каждым игроком каждое призовое место.
И да, вопрос не в стоимости одного билета, а в стоимости ВСЕХ билетов у каждого участника, ведь чем больше у участника билетов, тем дешевле каждый его билет по отдельности. Мы не можем купить несколько билетов у кого-то из игроков, мы должны покупать все. Суть в том, как посчитать математическое ожидание. А точнее - вероятность занять каждым игроком каждое призовое место.
>>39903 (OP)
1) В барабане, из которого извлекают номера выигрышных билетов, есть повторяющиеся номера?
2) Для любого ли номера, имеющегося в барабане, верно, что существует участник с билетом, имеющим этот номер? Если ответ на этот вопрос нет, то есть ли какое-то ограничение на количество номеров, лежащих в барабане?
3) Верно ли, что у всех лотерейных билетов различные номера?
4) Формализуй, что понимается под стоимостью билета.
1) В барабане, из которого извлекают номера выигрышных билетов, есть повторяющиеся номера?
2) Для любого ли номера, имеющегося в барабане, верно, что существует участник с билетом, имеющим этот номер? Если ответ на этот вопрос нет, то есть ли какое-то ограничение на количество номеров, лежащих в барабане?
3) Верно ли, что у всех лотерейных билетов различные номера?
4) Формализуй, что понимается под стоимостью билета.
>>43191
1) нет
2) каждому билету соответствует ровно один номер в барабане
3) верно
4) стоимости одного билета нет. В этой задаче речь идет о стоимости всех билетов каждого игрока. За сколько денег ты готов купить все билеты у кого-то из игроков? Понятно, что чем больше билетов ты покупаешь - тем больше денег можешь себе позволить заплатить.
1) нет
2) каждому билету соответствует ровно один номер в барабане
3) верно
4) стоимости одного билета нет. В этой задаче речь идет о стоимости всех билетов каждого игрока. За сколько денег ты готов купить все билеты у кого-то из игроков? Понятно, что чем больше билетов ты покупаешь - тем больше денег можешь себе позволить заплатить.
193x21Я приведу пример:
У трех игроков 3, 2, 1 билетов соответственно.
За первое место платят 3 йобы, за второе - 2 йобы, за третье 1 йобу.
В таком случае, три билета первого игрока стоят 2,35 йобы,два билета второго игрока стоят 2,066666667 йобы, один билет третьего игрока стоит 1,583333333 йобы.
Задача нихуя не тривиальная.
У трех игроков 3, 2, 1 билетов соответственно.
За первое место платят 3 йобы, за второе - 2 йобы, за третье 1 йобу.
В таком случае, три билета первого игрока стоят 2,35 йобы,два билета второго игрока стоят 2,066666667 йобы, один билет третьего игрока стоит 1,583333333 йобы.
Задача нихуя не тривиальная.
>>43196
И все билеты распроданы тем самым N участникам? Ну то есть не бывает такого, что номер в барабане нет, но билет с этим номером не принадлежит никому из рассматриваемых N участников?
> каждому билету соответствует ровно один номер в барабане
И все билеты распроданы тем самым N участникам? Ну то есть не бывает такого, что номер в барабане нет, но билет с этим номером не принадлежит никому из рассматриваемых N участников?
>>43239
Короче, пока хз, челикс. Какая-то нетривильная задачка. У меня для тебя есть странная идея - можешь попробовать поискать на codeforces задачи на вычисление математических ожиданий. Возможно там найдётся задача с похожей структурой.
Ещё есть тривильная идея. Если тебе не нужен точный ответ, то можешь попробовать монтекарлой посимулировать просто. Я правда хз, насколько быстро оно будет сходиться на этой задаче. Но это можно эмпирически проверить.
Короче, пока хз, челикс. Какая-то нетривильная задачка. У меня для тебя есть странная идея - можешь попробовать поискать на codeforces задачи на вычисление математических ожиданий. Возможно там найдётся задача с похожей структурой.
Ещё есть тривильная идея. Если тебе не нужен точный ответ, то можешь попробовать монтекарлой посимулировать просто. Я правда хз, насколько быстро оно будет сходиться на этой задаче. Но это можно эмпирически проверить.
Спасибо, бро, попробую поискать.
А насчет Монте-Карло - я пробовал, для N=10 погрешность 2%, что не есть гуд.
А насчет Монте-Карло - я пробовал, для N=10 погрешность 2%, что не есть гуд.
>>43197
Т.е. i-й игрок получает N йоб за Ai билетов? Че тут считать то тогда?
Если мы нумеруем игроков от 1 выигравшего, то стоимость одного i-го билета = (N + 1 - i) / Ai
Сумма всех билетов это сумма арифметической прогрессии (1 + N) * N /2
че еще считать? яннп
Т.е. i-й игрок получает N йоб за Ai билетов? Че тут считать то тогда?
Если мы нумеруем игроков от 1 выигравшего, то стоимость одного i-го билета = (N + 1 - i) / Ai
Сумма всех билетов это сумма арифметической прогрессии (1 + N) * N /2
че еще считать? яннп
>>43682
Да, я выпускник математического факультета. Где в условии написано про мат ожидание? Условие задачи поставлено максимально мутно, нигде не сказано что нужно перебрать всех участников и все комбинации выигрышей. А здесь вообще написано "три билета первого игрока стоят 2,35" но "первый игрок выиграл 3 йобы за 3 билета" что вообще выглядит как полная шиза. Поэтому мой ответ это тупо троллинг. И да когда мне на собесах что-то такое спрашивали, я просто нахуй посылал.
Да, я выпускник математического факультета. Где в условии написано про мат ожидание? Условие задачи поставлено максимально мутно, нигде не сказано что нужно перебрать всех участников и все комбинации выигрышей. А здесь вообще написано "три билета первого игрока стоят 2,35" но "первый игрок выиграл 3 йобы за 3 билета" что вообще выглядит как полная шиза. Поэтому мой ответ это тупо троллинг. И да когда мне на собесах что-то такое спрашивали, я просто нахуй посылал.
>>43685
Да, в условии задачи написана хуйня. Но если ты почитаешь сам тред, то условие там конкретизировалось. В частности, было указано, что нужно считать мат. ожидание.
При чём тут твои собесы.
//не ОП, если что
зы
Какого именно?
Бак, мага или кандидат?
По какой тебе зазищал дисер/диплом?
Да, в условии задачи написана хуйня. Но если ты почитаешь сам тред, то условие там конкретизировалось. В частности, было указано, что нужно считать мат. ожидание.
> И да когда мне на собесах что-то такое спрашивали, я просто нахуй посылал.
При чём тут твои собесы.
//не ОП, если что
зы
> Да, я выпускник математического факультета.
Какого именно?
Бак, мага или кандидат?
По какой тебе зазищал дисер/диплом?
>>43698
"... теме защищал ..."
"... теме защищал ..."
>>43703
Понятно, то есть к математике отношения не имеешь. Это точно математический факультет был, а не зашкваренная прикладная математика? А то тема уж больно на второе намекает.
> по теме поиска путей в автомобильном трафике
Понятно, то есть к математике отношения не имеешь. Это точно математический факультет был, а не зашкваренная прикладная математика? А то тема уж больно на второе намекает.
>>43706
Там суть была в том что под это система писалась на смолтоке. Факультет да, так и назывался, математический.
Собесы при том что эта тема выглядит как обиженка пришла с собеседования с этой задачей и вместо того, чтобы честно раскинуть мозгами, решила самоутвердиться потролив анона
Там суть была в том что под это система писалась на смолтоке. Факультет да, так и назывался, математический.
Собесы при том что эта тема выглядит как обиженка пришла с собеседования с этой задачей и вместо того, чтобы честно раскинуть мозгами, решила самоутвердиться потролив анона
>>43709
Я сомневаюсь, что его на собесе это спрашивали. У меня вообще есть смутное подозрение, что за полином в поставленном виде эта задача не решается. Возможно там можно с какой-то гарантией апроксимировать правильный ответ или выдать его с некоторой фиксированной вероятностью. Тут я хз, практические ничего не знаю про такие темы.
Я сомневаюсь, что его на собесе это спрашивали. У меня вообще есть смутное подозрение, что за полином в поставленном виде эта задача не решается. Возможно там можно с какой-то гарантией апроксимировать правильный ответ или выдать его с некоторой фиксированной вероятностью. Тут я хз, практические ничего не знаю про такие темы.
>>43722
Не знаю, что ты под этим подразумеваешь, но этот пример привёл оп, поэтому ответы, данные в этом сообщении можно считать правильными.
> это референсное решение
Не знаю, что ты под этим подразумеваешь, но этот пример привёл оп, поэтому ответы, данные в этом сообщении можно считать правильными.
Так я "решил" но пока N!
В принципе понятно как за 2 ^ N -1 решить
Суть такова, N-ю сумму заработают N игроков, независимо от их билетов, разницу между N-й и N-1 заработают N-1 игроков с вероятностью = сумма их весов и т.д, 1-й игрок заработает последнюю разницу со своим весом. Но ето перебор сочетаний ои 1 до N из N
Двач.hk прислал битые данные.
Вы видите копию треда, сохраненную 31 июля 2023 года.
Можете попробовать обновить страницу, чтобы увидеть актуальную версию.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Вы видите копию треда, сохраненную 31 июля 2023 года.
Можете попробовать обновить страницу, чтобы увидеть актуальную версию.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.