Этого треда уже нет.
Это копия, сохраненная 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
Тред утонул или удален.
Это копия, сохраненная 31 июля 2023 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.
Это копия, сохраненная 31 июля 2023 года.
Скачать тред: только с превью, с превью и прикрепленными файлами.
Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах. Подробнее
Если вам полезен архив М.Двача, пожертвуйте на оплату сервера.