1033 . 大黑馬(Underdog)
TopCoder
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
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 1
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 |