TopCoder

Thumb mikasa mikoto furikae
Omelet
$\Huge\mathcal A=(Q,\Sigma,\delta:Q\times\Sigma\to Q,s\in Q,F\subseteq Q)$

User's AC Ratio

91.1% (51/56)

Submission's AC Ratio

52.6% (92/175)

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

No. Testdata Range Score
1 0~4 20
2 5~9 20
3 10~14 20
4 15~19 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1
1 5000 524288 262144 1
2 5000 524288 262144 1
3 5000 524288 262144 1
4 5000 524288 262144 1
5 5000 524288 262144 2
6 5000 524288 262144 2
7 5000 524288 262144 2
8 5000 524288 262144 2
9 5000 524288 262144 2
10 5000 524288 262144 3
11 5000 524288 262144 3
12 5000 524288 262144 3
13 5000 524288 262144 3
14 5000 524288 262144 3
15 5000 524288 262144 4
16 5000 524288 262144 4
17 5000 524288 262144 4
18 5000 524288 262144 4
19 5000 524288 262144 4