#581 레이팅 갱신

問題を読み込み中...

本文、提出履歴、提出フォームを準備しています。

#581 레이팅 갱신

作問者: woohyunjng

Statement

問題文の言語

처음 레이팅은 $R_0$ 이다. 순서대로 $N$ 개의 대회에 참가하며, $i$ 번째 대회의 퍼포먼스는 $P_i$ 이다.

각 대회가 끝나면 이전 레이팅에 $3$ , 이번 퍼포먼스에 $1$ 의 가중치를 주어 레이팅을 갱신한다. $i$ 번째 대회가 끝난 뒤의 레이팅 $R_i$ 는 다음과 같다.

R_i=\frac{3R_{i-1}+P_i}{4}

모든 $i$ ( $1\leq i\leq N$ )에 대해 $R_i$ 는 양의 정수임이 보장된다.

모든 대회가 끝난 뒤의 레이팅 $R_N$ 을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ R_0$ $P_1\ P_2\ \cdots\ P_N$

$T$ 는 테스트 케이스의 수이다. 각 케이스에서 초기 레이팅 $R_0$ , 대회 수 $N$ , 그리고 대회 순서대로 $N$ 개의 퍼포먼스 $P_1,P_2,\cdots,P_N$ 이 주어진다.

각 테스트 케이스마다 한 줄에 최종 레이팅 $R_N$ 을 출력한다.

$1 \leq T \leq 100\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq R_0 \leq 5\cdot10^8$ .
$1 \leq P_i \leq 5\cdot10^8$ ( $1 \leq i \leq N$ ).
모든 대회가 끝난 뒤의 레이팅 $R_i$ 는 $1 \leq R_i \leq 5\cdot10^8$ 인 정수이다 ( $1 \leq i \leq N$ ).
모든 테스트 케이스에 대한 $N$ 의 합은 $200\,000$ 이하이다.

#	得点	制約
1	37	$P_i\geq R_{i-1}$ ( $1\leq i\leq N$ ).
2	63	추가적인 제약이 없다.

例 1

入力例

出力例

110
2
4

$1$ 번 케이스의 레이팅은 $100 \longrightarrow105 \longrightarrow 100 \longrightarrow 110$ 으로 변한다.

例 2

入力例

2
2 500000000
500000000 500000000
2 100
60 54

出力例

500000000
81

$1$ 번 케이스에서는 퍼포먼스와 현재 레이팅이 같아서 레이팅이 바뀌지 않는다. $2$ 번 케이스에서는 $100 \longrightarrow 90 \longrightarrow 81$ 로 변한다.