solved.ac 2022 difficulty rating

solved.ac is a community project that assigns difficulty ratings to problems on a programming problem-solving site. Before, the problems on that site had no difficulty labels, so it was hard to judge how hard a problem was before trying it. solved.ac was created to fix this. Since its launch, more than 1,900 contributors have shared difficulty opinions, and about 16,000 problems now have a rating.

The difficulty of a problem is decided from the difficulty opinions that users submitted for it. Previously, the difficulty was a simple trimmed mean that ignored when each opinion was submitted. Programming problem solving changes quickly, so solved.ac changed the formula to give newer opinions more weight. When a problem receives $N$ difficulty opinions, its difficulty is decided as follows.

• If there are no difficulty opinions, the difficulty of the problem is $0$.
• If there is at least one opinion, sort the opinions by submission time. Then the weight $p_i$ of each opinion is given by the following formula. $p_i=\max\left(0.5^{(t_N-t_i)/365\text{ days}},0.9^{N-i}\right)$
  • $t_i$ is the time when the $i$-th difficulty opinion was submitted. Since the opinions are sorted by time, $t_1\le t_2\le\cdots\le t_N$, and $t_N$ is the time of the most recent opinion.
• The difficulty $X$ of the problem is the weighted average with weights $p_i$, rounded to an integer at the first digit after the decimal point. $X=\frac{p_1l_1+p_2l_2+\cdots+p_Nl_N}{p_1+p_2+\cdots+p_N}=\frac{\sum_{i=1}^{N}p_il_i}{\sum_{i=1}^{N}p_i}$
  • $l_i$ is the difficulty in the $i$-th opinion, converted to an integer from $1$ to $30$. $1$ means Bronze 5, the lowest difficulty, and $30$ means Ruby 1, the highest difficulty.

The first line contains the number of difficulty opinions $N$. $(0\le N\le 1\,000)$

From the second line, the next $N$ lines each contain one difficulty opinion. The $i$-th of these lines contains $t_i$ and $l_i$, separated by a space.

• $t_i$ is the time when the difficulty opinion was submitted. It is in the format year/month/day hour:minute:second.

  • The year has 4 digits. The month, day, hour, minute, and second each have 2 digits, and a leading $0$ may be added to fill the width. In particular, $2020$ is a leap year, so February has 29 days in $2020$.
  • Time uses the 24-hour format.
  • The given times range from 00:00:00 on June 6, 2019 to 23:59:59 on July 1, 2022. The times are sorted so that $t_1\le t_2\le\cdots\le t_N$.

• $l_i$ is the difficulty value of the opinion, an integer. $(1\le l_i\le 30)$

Print the difficulty calculated from the given opinions. The answer is accepted if the printed integer differs from the unrounded weighted average computed by the checker by at most $0.5+10^{-5}=0.50001$.

In the first case, the first opinion was submitted about 834 days and 6 hours, or about $2.286$ years, before the last opinion. So the weighted average is $X\approx\frac{\max\left(0.5^{2.286},0.9^1\right)\times 24+\max\left(0.5^0,0.9^0\right)\times 18}{\max\left(0.5^{2.286},0.9^1\right)+\max\left(0.5^0,0.9^0\right)}=\frac{0.9\times 24+1\times 18}{0.9+1}\approx 20.842$ Rounding this gives $21$, which is the difficulty.