Описание задачи
Рассчитать вероятность того, что сумма чисел, вытянутых из N урн, будет равна sum. Условие:
подряд не более k одинаковых чисел.
Формат входных данных
> Bins (Count):
N
> Intervals (Lo Hi):
lo1 hi1
lo2 hi2
...
> Queries (Sum Max_Repetitions):
sum k
Формат выходных данных
Probability: числитель/знаменатель
Дробь должна быть в несократимом виде.
Примеры
Конфигурация
> Bins: 3
> Intervals:
1 6
1 8
1 4
Запросы
5 3 → Probability: 1/32 5 1 → Probability: 1/96 9 3 → Probability: 7/64 9 2 → Probability: 5/48 9 1 → Probability: 17/192
Ключевые моменты
- Рекурсия: (урна, сумма, последнее_число, счётчик_повторений)
- Мемоизация обязательна
- Общее количество исходов = произведение размеров диапазонов
- Сокращение дроби через НОД