25318번 - solved.ac 2022 스페셜 저지

solved.ac는 프로그래밍 문제해결 사이트 백준 온라인 저지에 있는 문제들에 난이도를 붙이는 커뮤니티 프로젝트다. 기존에는 백준 온라인 저지의 문제들에 난이도 표기가 없어서, 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 만들어졌다. solved.ac가 생긴 이후 $1\, 900$명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 $16\, 000$문제에 난이도가 붙게 되었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 기존에는 의견이 제출된 시점과 상관 없이 단순 절사평균으로 난이도를 결정했으나, 프로그래밍 문제 해결은 빠르게 변하는 분야이기 때문에 solved.ac는 새로운 의견들을 더 무겁게 반영하고자 난이도 산정 공식을 바꾸기로 했다. 어떤 문제에 $N$개의 난이도 의견이 제출되었을 때 문제의 난이도는 아래와 같은 방법으로 결정한다.

• 난이도 의견이 하나도 없다면 문제의 난이도는 $0$으로 한다.
• 난이도 의견이 하나 이상 있는 경우, 의견들을 제출한 시각에 따라 정렬한 뒤 각 의견의 가중치 $p_i$를 다음 수식으로 결정한다.\[p_i=\max\left( 0.5^{\left( t_N-t_i \right) /365\text{일}},0.9^{N-i} \right)\]
  • $t_i$는 $i$번째 난이도 의견이 제출된 시각을 의미한다. 시간 순으로 정렬했으므로 $t_1\le t_2\le\cdots\le t_N$이며, $t_N$은 가장 최근 제출된 의견의 제출 시각이 된다.
• 문제의 난이도 $X$는 $p_i$를 가중치로 갖는 가중평균을 소수점 아래 첫 번째 자리에서 반올림해 정수로 나타낸 것이다. \[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$는 $i$번째 의견에 담긴 난이도를 $1$ 이상 $30$ 이하의 정수로 바꾼 값이다. $1$은 가장 낮은 난이도인 브론즈 $5$를, $30$은 가장 높은 난이도인 루비 $1$을 가리킨다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

첫 번째 줄에 난이도 의견의 개수 $N$이 주어진다. $(0\le N\le 1\, 000)$

이후 두 번째 줄부터 다음 $N$개의 줄에 걸쳐 각 줄마다 난이도 의견이 하나씩 주어진다. 주어지는 $N$개 줄 중 $i$번째 줄에는 $t_i$와 $l_i$가 공백으로 구분되어 주어진다.

• $t_i$는 난이도 의견이 남겨진 시각으로, 연도/월/일 시:분:초 형식이다.
  • 연도는 $4$자리, 월/일/시/분/초는 각각 $2$자리의 문자열이며 필요한 경우 자릿수를 맞추기 위해 숫자 $0$이 앞에 붙을 수 있다. 특히 $2020$년은 윤년이므로, $2020$년의 경우 $2$월의 마지막 날이 $29$일이다.
  • 시간은 $24$시간 형식이다.
  • 주어지는 시각은 $2019$년 $6$월 $6$일 $00:00:00$부터 $2022$년 $7$월 $1$일 $23:59:59$까지이며, $t_1\le t_2\le\cdots\le t_N$이 되도록 정렬되어 있다.
• $l_i$는 난이도 의견의 값을 의미하는 정수이다. $(1\le l_i\le 30)$

주어진 난이도 의견들을 바탕으로 계산된 난이도를 출력한다. 출력한 정수가 채점 프로그램이 계산한 반올림하기 전의 가중평균과 $0.5+10^{-5}=0.50001$ 이하의 차이가 발생하는 경우에 정답으로 인정한다.

첫 번째 경우에서 첫 번째 의견은 마지막 의견에 비해 약 $834$일 $6$시간$\,\approx 2.286$년 전 의견이므로, 가중평균은 \[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\]
이다. 따라서 난이도는 이를 반올림한 $21$로 결정된다.