Алгоритм, связанный с нахождением вероятности

Question

Это не работа, это проблема, с которой я столкнулся в конкурсе программистов, но не смог найти решение.

Королевство Байтленд содержит N городов с номерами 1..N. Для каждого города я король назначает этому городу деньги на его ежегодное обслуживание. Назначенная сумма выбирается случайным образом между ai (минимальная сумма, необходимая для этого города) и bi (максимальная сумма, которая может быть назначена этому городу). Обратите внимание, что сумма, назначенная городу, не обязательно должна быть целым числом. Общий налог, собранный в этом году, составляет C.

Какова вероятность того, что королевство выдаст убыток в этом году

Answer 1

Я предполагаю, что это правильное утверждение:

Королевство Байтленд содержит N городов с номерами 1..N. Для каждого города я король назначает этому городу деньги на его ежегодное обслуживание. Назначенная сумма выбирается случайным образом между ai (минимальная сумма, необходимая для этого города) и bi (максимальная сумма, которая может быть назначена этому городу). Обратите внимание, что сумма, назначенная городу, не обязательно должна быть целым числом. Общий налог, собранный в этом году, составляет C.

Какова вероятность того, что королевство допустит убыток в этом году? Другими словами, какова вероятность того, что общая сумма, назначенная всем городам, превысит общую сумму налога?

сумма всего назначения равна x_0 + ... + x_i + ... + x_n. Если U(a,b) является равномерным числом между a и b, сумма всех назначений U(0, b_0 - a_0) + a_0 + ... + U(0, b_i - a_i) + a_i + ... + U(0, b_n - a_n) + a_n, что равно a_0 + ... + a_i + ... + a_n + U(0, b_0 - a_0) + ... + U(0, b_i - a_i) + ... + U(0, b_n - a_n) все значения известны. Формула для добавления равномерных распределений также известна ( см. Здесь): но в задаче программирования вам не нужно использовать аналитическое решение, а реализовать что-то, что дает вам достаточно хорошее число... Вы должны использовать montecarlo или что-то вроде что имитировать вероятности... И вы также можете использовать тот факт, что U(0, k) = k * U(0, 1). Рассчитать вероятность различных значений суммы, а затем сравнить их с C.