Недавно вышедшая книга получает оценки читателей по шкале от $$$1$$$ до $$$n$$$. Читатели оставляют отзывы по очереди, а рейтинг книги в каждый момент равен среднему арифметическому всех уже поставленных оценок.
Для каждого читателя известны его тип $$$t_i$$$ и желаемый рейтинг $$$x_i$$$.
Если $$$t_i = \texttt{S}$$$, то читатель всегда ставит книге оценку $$$x_i$$$.
Если $$$t_i = \texttt{D}$$$, то перед голосованием читатель видит текущий рейтинг книги и число уже проголосовавших читателей. Затем он выбирает целую оценку от $$$1$$$ до $$$n$$$ так, чтобы рейтинг книги после его голоса был как можно ближе к $$$x_i$$$.
Организаторы могут выбрать любой порядок, в котором читатели будут оставлять отзывы.
$$$\texttt{Andrew-13}$$$ стало интересно, какими минимальным и максимальным итоговыми рейтингами может обладать книга. Найдите эти значения.
В первой строке входных данных содержится 2 числа $$$n, m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — максимальная возможная оценка книги и количество читателей соответственно.
В каждой из следующих $$$m$$$ строк содержатся символ $$$t_i$$$ ($$$t_i = \texttt{S}$$$ или $$$t_i = \texttt{D}$$$) и целое число $$$x_i$$$ $$$(1 \le x_i \le n)$$$ — тип читателя и желаемый им рейтинг.
Символ $$$t_i$$$ равен $$$\texttt{S}$$$, если читатель всегда ставит оценку $$$x_i$$$, или $$$\texttt{D}$$$, если читатель выбирает оценку так, чтобы итоговый рейтинг после его голоса был как можно ближе к $$$x_i$$$.
В единственной строке выведите два числа — минимальный и максимальный итоговые рейтинги книги.
Ваш ответ считается верным, если его абсолютная или относительная погрешность не превышает $$$10^{-9}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри – $$$b$$$. Ваш ответ считается правильным, если $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$$$.
10 3S 3S 5D 8
5.3333333333333 6.0000000000000
1000 4D 999D 101S 323D 812
487.0000000000000 606.0000000000000
| Осенний кубок МИФИ 2026 |
|---|
| Закончено |
