TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Description

osu! 是一款可以在電腦上玩的音樂遊戲。玩家可以透過遊玩歌曲,並依照所獲得的分數和準確率得到一個名為 PP (Performance Points) 的點數,而這個點數就是排名的依據,PP 越高,排名越前面。

然而 osu! 的每個模式的計分方法並不盡然相同,也牽涉到了許多不同的參數,所以在此問題中只考慮為了題目而特別設計過的 Osu! mania 計分方法。

首先,每個 osu! mania 的 note (玩家必須點擊的物件)在被擊中時會依據擊中的時間點和該 note 預設被擊中的時間點的差距被分為以下幾種判定:Rainbow 300(以下簡稱 MAX),300,200,100,50。其中,定義每種判定的 HitValue 分別是 320,300,200,100,50 以及 HitPunishment 分別是 0,$p_{300}$,$p_{200}$,$p_{100}$,$p_{50}$。

再來,定義每個 note 的 Punishment 。一開始,每個 note 的這個值是 $0$。一旦得到了不是 MAX 的判定,就會使從下一個 note 開始的連續 HitPunishment 個 note 的 Punishment 增加 $1$。舉個例子,如果 $p_{300} = 2, p_{200} = 5$,那麼假設這首歌共有 $10$ 個 note,且判定分別為 MAX、200、MAX、300、300、MAX、MAX、MAX、200、MAX 的話 Punishment 分別就會是 0、0、1、1、2、3、2、0、0、1。注意倒數第二個 note 的 200,理論上它應該會讓它之後的 5 個 note 的 Punishment 增加,可是因為後面沒有那麼多 note ,所以就只作用到最後一顆 note 為止。

最後是算分數的方法。最終的分數 $S$ 是依據把每個 note 的分數加總而成的。定義每個 note 的分數 $S_i = \frac{HitValue}{320} \times (0.99)^ {Punishment} \times \frac{1000000}{NoteCount}$,而NoteCount 就是整首歌的 note 數量。

現在,一名高手玩家面對著長達 $1000$ 分鐘的耐力型歌曲,總 note 數量更是驚人之多。他想在開始這首歌之前知道,如果某些 note 他不幸的沒有打出 MAX 的話,他最後的成績會是多少?給定總 note 數量 $N$ 以及每種判定的 HitPunishment ,假設一開始對於所有 note 的判定都是 MAX,對於他的每個疑問「如果第 $i$ 個 note 的判定變成 $X$ 之後,歌曲結束時我的總分會是多少?」回答他的問題。在此問題中,疑問是持久的。舉例來說,在第五個疑問發生時,第一個到第四個疑問所造成的判定改變也應該被記入這個疑問的考慮範圍當中。如果當中對於同一個 note 有不同的判定的疑問的話,以最新的那個疑問為主。

此外,不用考慮沒有擊中的情況。

Input Format

第一行有一個正整數 $T$,代表總共有幾筆測試資料。
每一筆測試資料,第一行會有 6 個整數,分別為 $N, Q, p_{300}, p_{200}, p_{100}, p_{50}$。
之後會有 $Q$ 行,每行會有兩個數字 $i, v$,代表第 $i$ 個 note 的判定變成 HitValue 為 $v$ 的判定 $X$。

  • $T \leq 5$
  • $1 \leq N, Q \leq 100000$
  • $0 \leq p_{300}, p_{200}, p_{100}, p_{50} \leq 100000$
  • $1 \leq i \leq N$
  • $v \in {50, 100, 200, 300, 320}$

Output Format

對於每個疑問,請輸出一行,代表對於這個疑問的答案。你輸出的數字跟答案只要相對誤差或絕對誤差在 $10^ {-9}$ 以內都算正確。

亦即,若正確答案為 $a$ ,你輸出的數字為 $b$ ,只要 $\frac{|a - b|}{\max(1, a)} < 10^ {-9}$ 就會被視為正確。

Sample Input

1
5 2 0 0 0 2
2 100
2 300

Sample Output

862500.000000123456789
987500.000000987654321

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 262144 262144
1 4000 262144 262144
2 4000 262144 262144
3 4000 262144 262144
4 4000 262144 262144
5 4000 262144 262144
6 4000 262144 262144
7 4000 262144 262144
8 4000 262144 262144
9 4000 262144 262144
10 4000 262144 262144
11 4000 262144 262144
12 4000 262144 262144