TopCoder

User's AC Ratio

83.3% (10/12)

Submission's AC Ratio

41.5% (22/53)

Description

在某個校際球賽中,兩隊對決時每隊各派出奇數(2K+1)位選手進行2K+1 場單打(不可重覆),贏得K+1 場或以上的隊伍勝出。每位選手的實力以BP 積分來表示,每場單打時積分較高的選手一定獲勝。然而因為賽程的安排,有時實力組合較強的一隊未必能勝出,例如A 隊有積分為100, 80, 60 的三位選手,依序遭遇B 隊積分為90, 70, 50 的選手,將以
3:0 戰績獲勝, 但若依序遭遇B 隊積分為50, 90, 70 的選手,則反而將以1:2 戰績落敗。主辦單位將各隊選手的BP 積分加總,依序決定各隊的種子順序,總積分最高的為第
一種子。為了簡化問題,我們排除總積分相同的情況。而兩位BP 積分相同的選手對決時,則該場單打由來自總積分較高的隊伍獲勝。
然而,在實際賽程中,選手的表現偶有異常(突出或失誤)的表現,導致個別的實力(BP積分)突然上升或下降,這些異常的表現也必須列入考慮。例如在下列的範例中,第三種
子隊伍表現突出時,即可能擊敗其他兩隊。某校的球隊是著名的黑馬,他們選手實力組合未必最強,但是卻經常意外擊敗實力組合堅強的隊伍。也就是說,他們雖然種子順序不高,卻經常爆出冷門,打敗種子順序超前許多的隊伍。請找出今年參賽的隊伍中,可能成為今年冠軍的最大黑馬。也就是,在有機會擊敗所有對手的隊伍中,且不論機率多低,總積分最少的一隊(也就是種子順序數值最大的一隊)。

Input Format

第一行輸入K 和N,以空白分開,代表每隊有2K+1 位選手,參賽隊伍數為N。
第二行開始有N 行,每一行有1+3*(2K+1)個整數$S,P_1, P_2,\dots , P_{2K+1}, U_1, U_2, \dots ,U_{2K+1}, L_1,L_2,\dots , L_{2K+1}$,中間以空白區隔,表示種子順序S 的隊伍由積分$P_1, P_2,\dots, P_{2k+1}$ 的2K+1 位
選手組成,為了簡化資料輸入的問題,$P_1, P_2,\dots, P_{2k+1}$ 由大至小排列,也就是$P_1 \geq P_2 \geq \dots \geq P_{2K+1}$,而這些選手表現突出時,實力相當於$U_1, U_2, \dots, U_{2K+1}$,但是表現失常時,實力則相當於$L_1,L_2,\dots , L_{2K+1}$,且$U_i \geq P_i \geq L_i$。為了簡化問題,$U_1 \geq U_2 \geq \dots ≥ U_{2K+1}$ 和$L_1 \geq L_2 \geq \dots \geq L_{2K+1}$ 也一定成立。

Output Format

每筆測試資料輸出一行,包含兩個數字$S_1, S_2$,中間以空白分開,代表若每位選手都
無異常表現時,大黑馬是種子順序$S_1$ 的隊伍,但若考慮每位選手各種可能的異常表現時,大黑馬是種子順序$S_2$ 的隊伍。

Sample Input

1 3
1 100 80 60 100 80 60 100 80 60
2 90 70 50 100 80 60 90 70 50
3 80 60 40 100 80 60 70 50 30

Sample Output

2 3

Hints

本題共有四組測試資料。
第一組測試資料 $K \leq 2,N \leq 10,U_i = P_i = L_i$,共 20 分。
第二組測試資料 $K \leq 2,N \leq 15,U_i \geq P_i \geq L_i$,共 20 分。
第三組測試資料 $K \leq 5,N \leq 25,U_i \geq P_i \geq L_i$,共 20 分。
第四組測試資料 $K \leq 5$,$N \leq 50$,$U_i \geq P_i \geq L_i$,共 40 分。

註:北市賽中不能使用long long型別。

Problem Source

臺北市104 學年度高級中學資訊學科能力競賽程式設計試題第三題
Set by Paupière
若測資有誤請儘快聯絡管管(?

Subtasks

For Testdata: 0 ~ 4, Score: 20
For Testdata: 5 ~ 9, Score: 20
For Testdata: 10 ~ 14, Score: 20
For Testdata: 15 ~ 19, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 524288 65536
1 5000 524288 65536
2 5000 524288 65536
3 5000 524288 65536
4 5000 524288 65536
5 5000 524288 65536
6 5000 524288 65536
7 5000 524288 65536
8 5000 524288 65536
9 5000 524288 65536
10 5000 524288 65536
11 5000 524288 65536
12 5000 524288 65536
13 5000 524288 65536
14 5000 524288 65536
15 5000 524288 65536
16 5000 524288 65536
17 5000 524288 65536
18 5000 524288 65536
19 5000 524288 65536