TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

74.1% (20/27)

Submission's AC Ratio

51.4% (37/72)

Description

ACM-ICPC賽制是目前最常見的團體程式競賽模式,每隊由三個隊員組成,隊員需合力在只使用一台電腦的情況下,在五個小時(300分鐘)的比賽中解出盡量多的題目,並且儘早地用盡量少的嘗試次數解決題目。

每個隊伍將會面對至多15道題目,與高中奧林匹亞競賽不同的是,題目是沒有部分分的,也就是每道題目只有「解出」和「未解出」兩種結果,並以每隊有解出的題目數量進行排名,解出愈多題則排名愈前面。
當然,若只考慮解出題數勢必會造成大量的並列,所以ACM-ICPC賽制引入了「罰時」的機制:若一個隊伍在比賽開始後$T$分鐘時首次解出一道題目$x$,將獲得$T+20W$分鐘的罰時,其中$W$是在此之前(不包含本次)這個隊伍總共在該道題上傳了幾次程式碼(注意到一旦一個隊伍解出某題後,之後任何不管正確或是錯誤的上傳紀錄將不會對該題的罰時造成影響),一個隊伍的總罰時即是所有獲得罰時的加總。
若兩個隊伍解出的題目數量相同,則罰時愈少者排名愈前面。若兩個隊伍解出題目數量和罰時均相同,則視為並列(注意此處為了簡化問題,規則與實際比賽有所出入)。一個隊伍的名次即是有多少隊伍排名比該隊伍前面加一,例如若所有隊伍並列,則所有隊伍均獲得第一名。

以下用一個隊伍整場比賽的上傳紀錄來做舉例說明:

時間 題目 是否解出
3 A
5 B
6 A
10 C
298 B
299 B

則此隊最終的結果為解出兩題(A、B),並且在題目A的罰時為$6+20\times 1 =26$分鐘,在題目B的罰時為$5+20\times 0=5$分鐘,總罰時為31分鐘。請注意雖然此隊上傳了一個未解出C題的程式碼,但由於此隊未有解出題目C,此上傳紀錄將不會造成總罰時的提升;另外雖然此隊在298、299分鐘時再度上傳了B題的程式碼,但由於並非首次解出,所以不會得到額外的罰時。

團體競賽雖然相當有趣又刺激,但準備一場萬無一失的比賽也相當不容易,一旦測資有疏失,將可能造成許多問題:例如一個隊伍可能上傳了正確的程式碼並未解出那題,也可能上傳了錯誤的程式碼卻意外解出題目,更有可能一開始上傳了正確的程式碼獲得了錯誤的評測結果、不斷修正後猜出主辦單位的錯誤並解出該題,然而卻因此獲得巨量的罰時。

剛踏入資訊競賽圈子的盩僰麌也剛參加了一場這樣的團體競賽。
具體來說,這場比賽共有$N$隊參加(編號為$0$到$N - 1$),每隊有$M$題要解決(編號為$0$到$M - 1$),而盩僰麌的隊伍編號為$0$。

然而,這場比賽的每一道題目的測資都有問題,而這也造成盩僰麌的隊伍的比賽成績不盡理想。為了討回演算法的正義(以及豐厚的獎金),盩僰麌搜集了整場比賽的所有上傳紀錄,包括上傳時間、題號、在比賽中是否解出(也就是在測資錯誤的情況下),並且按照上傳時間排列。除此之外,他也以正確的測資評測了每一筆上傳紀錄的程式碼,因此盩僰麌也知道該筆上傳紀錄是否能在測資正確的情況下解出該題。
雖然照理來說主辦方該更新每一題的測資並重新評測每一題,但這個比賽規模之大,主辦方的伺服器只能承受至多重新評測$K$題。

事關比賽獎金,精打細算的盩僰麌想知道,在最多重新評測$K$題的情況下,自己的隊伍最高能獲得的名次為何?

Input Format

輸入第一行為一個正整數$T$,代表有幾組測資。
每組測資以三個非負整數$N, M, S, K$為第一行。
接著$S$行每行有5個非負整數$t_i, g_i, p_i, a_i, b_i$分別代表整場比賽第$i$個上傳紀錄的時間(分鐘)、傳送的隊伍、傳送的題號、得到的結果(在測資錯誤的情況下)、實際的結果(在測資正確的情況下),其中$t_i \leq 300; g_i < N; p_i < M; a_i, b_i \in \{0, 1\}$(1代表解出、0代表未解出)。

對於所有的測資,$T\leq 10, N \leq 100, K\leq M \leq 15, S \leq 10^ 4$,且保證一隊在同一分鐘最多只會上傳同一題一次

Output Format

輸出一個正整數代表在最多重新評測$K$題的情況下,盩僰麌的隊伍的最高名次為何(名次最小)。

Sample Input

5
3 2 5 3
1 0 0 1 0
1 1 0 0 1
2 1 1 1 0
3 0 1 0 1
4 2 1 1 1
2 3 4 1
1 1 0 1 0
2 1 1 1 0
100 0 0 0 0
299 0 0 0 1
3 2 6 1
7 2 0 1 1
8 2 1 1 1
10 1 0 1 0
11 0 0 1 0
18 0 1 1 1
20 1 1 1 1
4 2 5 2
1 1 0 1 1
10 2 0 1 1
100 3 0 1 1
298 0 0 1 0
299 0 1 1 1
3 2 2 2
87 2 1 1 0
123 1 0 1 1

Sample Output

1
2
2
1
2

Hints

範例測資一中,最好的方法是重新評測第1題,如此一來第0隊答對2題、罰時4分鐘,第1隊答對0題、罰時0分鐘,第2隊答對1題、罰時4分鐘。
範例測資五中,雖然盩僰麌的隊伍一題都未解出,卻可以透過重新評測第1題使第2隊與自己並列,提高排名。

Problem Source

Problem set by waynetuinfor
建國中學107學年度校隊選拔:初試pA

Subtasks

No. Testdata Range Constraints Score
1 0~14 $K = 0$ 21
2 15~29 $S \leq 100$ 30
3 0~49 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1 3
1 2000 262144 262144 1 3
2 2000 262144 262144 1 3
3 2000 262144 262144 1 3
4 2000 262144 262144 1 3
5 2000 262144 262144 1 3
6 2000 262144 262144 1 3
7 2000 262144 262144 1 3
8 2000 262144 262144 1 3
9 2000 262144 262144 1 3
10 2000 262144 262144 1 3
11 2000 262144 262144 1 3
12 2000 262144 262144 1 3
13 2000 262144 262144 1 3
14 2000 262144 262144 1 3
15 2000 262144 262144 2 3
16 2000 262144 262144 2 3
17 2000 262144 262144 2 3
18 2000 262144 262144 2 3
19 2000 262144 262144 2 3
20 2000 262144 262144 2 3
21 2000 262144 262144 2 3
22 2000 262144 262144 2 3
23 2000 262144 262144 2 3
24 2000 262144 262144 2 3
25 2000 262144 262144 2 3
26 2000 262144 262144 2 3
27 2000 262144 262144 2 3
28 2000 262144 262144 2 3
29 2000 262144 262144 2 3
30 2000 262144 262144 3
31 2000 262144 262144 3
32 2000 262144 262144 3
33 2000 262144 262144 3
34 2000 262144 262144 3
35 2000 262144 262144 3
36 2000 262144 262144 3
37 2000 262144 262144 3
38 2000 262144 262144 3
39 2000 262144 262144 3
40 2000 262144 262144 3
41 2000 262144 262144 3
42 2000 262144 262144 3
43 2000 262144 262144 3
44 2000 262144 262144 3
45 2000 262144 262144 3
46 2000 262144 262144 3
47 2000 262144 262144 3
48 2000 262144 262144 3
49 2000 262144 262144 3