Задача №115393. Много игр
Недавно вы получили редчайший билет в единственное казино в мире, в котором и правда можно что-то заработать, и вы хотите на полную воспользоваться этой возможностью.
Условия в этом казино следующие:
- В казино есть \(n\) игр, в которые предлагается сыграть.
- В каждую из игр можно сыграть не более одного раза.
- Каждая игра характеризуется двумя параметрами: \(p_i\) (\(1 \le p_i \le 100\)) и \(w_i\) — вероятность победы в игре в процентах и выигрыш за победу.
-
Если вы проиграете хоть в одну игру, в которую решите сыграть, — вы не получите вообще ничего (даже за выигранные игры).
Вам нужно заранее выбрать набор игр, в которые вы будете играть, таким образом, чтобы максимизировать \(\textbf{матожидание}\) выигрыша в казино.
В данном случае, если вы выберете игры с индексами \(i_1, \dots, i_k\), то вы выиграете во все из них с вероятностью \(\prod\limits_{j=1}^k \frac {p_{i_j}}{100}\), и в таком случае получите \(\sum\limits_{j=1}^k w_{i_j}\) выигрыша.
То есть \(\textbf{матожидание}\) вашего выигрыша будет \(\left(\prod\limits_{j=1}^k \frac {p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)\).
Чтобы не разориться, владельцы казино поставили ограничение матожидания выигрыша каждой отдельной игры, так что для любого \(i\) выполнено \(w_i \cdot p_i \le 200\,000\).
Ваша задача — найти максимальное матожидание выигрыша, которое можно получить, выбрав какое-то подмножество игр в казино.
В первой строке входных данных дано одно целое число \(n\) \((1 \le n \le 200\,000)\) — количество игр, в которые предлагается сыграть.
В следующих \(n\) строках находятся по два целых числа \(p_i, w_i\) (\(1 \leq p_i \leq 100\), \(1 \leq w_i\), \(p_i \cdot w_i \leq 200\,000\)) — вероятность победы и размер выигрыша в \(i\)-й игре.
Выведите одно число — максимальное матожидание выигрыша в казино, которое можно получить, выбрав некоторое подмножество игр.
Ответ будет принят, если его абсолютная или относительная погрешность не превосходит \(10^{-6}\).
В первом примере нужно выбрать первую и третью игры. В таком случае матожидание выигрыша будет \((\frac{80}{100}\cdot \frac{50}{100}) \cdot (80 + 200) = 112\).
3 80 80 70 100 50 200
112.00000000