Честный интервал для озера
Эколог оценивает площадь водоёмов по спутниковым снимкам: бросает на кадр площадью A км² n случайных точек и считает, сколько из них, k, попало в воду. Оценка площади — A · k/n. К ней нужен 95-процентный доверительный интервал.
Учебная формула p̂ ± z√(p̂(1 − p̂)/n) эколога не устраивает: если в маленький пруд не попала ни одна точка, она утверждает, что воды нет наверняка. Поэтому интервалом договорились считать все доли воды p от 0 до 1, при которых наблюдённая доля p̂ = k/n отличается от p не больше чем на z стандартных отклонений, посчитанных по самому p:
$$\left|\hat p - p\right| \le z\sqrt{\frac{p(1-p)}{n}}, \qquad z = 1{,}959963984540054.$$Выведите оценку площади и концы интервала в квадратных километрах (долю, умноженную на A).
Вход
В первой строке число водоёмов q (1 ≤ q ≤ 5000). В каждой из следующих q строк — вещественное A (0 < A ≤ 10⁶) и целые n, k (1 ≤ n ≤ 10⁹, 0 ≤ k ≤ n).
Выход
Для каждого водоёма — три числа через пробел: оценку площади, нижний и верхний конец интервала. Каждое число принимается с абсолютной или относительной погрешностью 10⁻⁶.
Примеры
Пример 1
3 3517.5 1000 312 12.5 30 0 2.0 10 10
1097.460000000 999.144770830 1200.836423408 0.000000000 0.000000000 1.418917415 2.000000000 1.444934400 2.000000000
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Неравенство с модулем и корнем неудобно. Обе его части неотрицательны — что будет, если возвести их в квадрат?
2Подсказка 2
После возведения в квадрат получится (p̂ − p)² ≤ z²p(1 − p)/n — квадратное неравенство относительно p с положительным старшим коэффициентом. Где такое неравенство выполняется?
3Идея
Раскроем скобки и соберём всё по степеням p: (1 + z²/n) p² − (2p̂ + z²/n) p + p̂² ≤ 0. Парабола смотрит вверх, поэтому неравенство верно между её корнями — это и есть интервал. Он называется интервалом Уилсона, по Эдвину Уилсону, который предложил его в 1927 году; подробнее — в статье о методе Монте-Карло.
4Разбор
Корни квадратного уравнения после упрощения:
$$p_{\pm} = \frac{\hat p + \frac{z^2}{2n} \pm z\sqrt{\frac{\hat p(1-\hat p)}{n} + \frac{z^2}{4n^2}}}{1 + \frac{z^2}{n}}.$$Дискриминант всегда положителен, так что корень извлекается без проверок. При k = 0 нижний конец ровно 0, а верхний положителен: даже не поймав ни одной точки в воде, мы не утверждаем, что воды нет. При k = n верхний конец ровно 1. Из-за округления концы могут чуть выйти за [0, 1] — обрежьте их.
Во втором тесте — счётчики из статьи: точки, брошенные на настоящую маску воды Капчагайского водохранилища. Сравните интервалы с теми, что печатает программа в статье.
4+Решение
5Сложность
O(1) на водоём: несколько арифметических действий и один корень.
6Типичные ошибки
- Учебная формула. При k = 0 даёт интервал [0, 0], при k = n — [1, 1]. Уже второй водоём первого примера её ловит.
- Подставить p̂ под корень. Если в правой части неравенства заменить p на p̂, получится та же учебная формула — весь смысл в том, что разброс считается по проверяемому p.
- Целочисленное деление. k/n в Go при целых k и n — ноль. И n до 10⁹: n² в знаменателе не помещается в 32 бита, считайте в вещественных числах.