1033 . 大黑馬(Underdog)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

93.2% (109/117)

Submission's AC Ratio

49.2% (184/374)

Tags

北市賽 2015-北市賽 greedy

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,P1,P2,…,P2K+1,U1,U2,…,U2K+1,L1,L2,…,L2K+1，中間以空白區隔，表示種子順序S 的隊伍由積分P1,P2,…,P2k+1 的2K+1 位
選手組成，為了簡化資料輸入的問題，P1,P2,…,P2k+1 由大至小排列，也就是P1≥P2≥⋯≥P2K+1，而這些選手表現突出時，實力相當於U1,U2,…,U2K+1，但是表現失常時，實力則相當於L1,L2,…,L2K+1，且Ui≥Pi≥Li。為了簡化問題，U1≥U2≥⋯≥U2K+1 和L1≥L2≥⋯≥L2K+1 也一定成立。

Output Format

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

Sample Input 1

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 1

2 3

Hints

本題共有四組測試資料。
第一組測試資料 K≤2，N≤10，Ui=Pi=Li，共 20 分。
第二組測試資料 K≤2，N≤15，Ui≥Pi≥Li，共 20 分。
第三組測試資料 K≤5，N≤25，Ui≥Pi≥Li，共 20 分。
第四組測試資料 K≤5，N≤50，Ui≥Pi≥Li，共 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 (VSS, 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
Submit
Back to Top