運動積分 題解|APCS 2026 年 10 月中級 第 3 題


簡潔題意

\(N\) 位選手(編號 \(1\)~\(N\))比賽 \(K\) 天,每天記錄每位選手步行、跑步、騎自行車各幾分鐘。選手一天的日積分是:步行每滿 \(10\) 分鐘得 \(X\) 分、跑步每滿 \(10\) 分鐘得 \(Y\) 分、騎自行車每滿 \(10\) 分鐘得 \(Z\) 分,三項加起來(不滿 \(10\) 分鐘的部分不得分)。每天日積分最高的選手加 \(A\) 分、最低的扣 \(B\) 分;從第 \(2\) 天起,日積分大於自己前一天日積分的選手再加 \(S\) 分。總積分是 \(K\) 天日積分的總和,加上所有加分、減去所有扣分;輸出總積分最高的選手編號和他的總積分(\(2 \le N \le 20\),\(1 \le K \le 20\),\(1 \le X, Y, Z, A, B, S \le 10\),分鐘數都是 \(0\) 到 \(120\) 的整數;同一天所有選手的日積分互不相同,所有選手的總積分也互不相同)。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(60\) 分):\(N = 2\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):先存成一張表,兩個人直接比

先讀完、存成一張表。加分扣分要比同一天的所有選手,輸入卻是一位選手一行:讀完選手 \(1\) 那一行時,還不知道其他人第 \(1\) 天的日積分。所以先把每位選手每一天的日積分算好,存進二維陣列 daily(語法書 6.9):daily[i][d] 是選手 \(i\) 第 \(d\) 天的日積分,選手和天數都從 \(1\) 用起、各多開一格(語法書 6.3)。輸入的一行剛好是這張表的一列,讀的時候外層迴圈跑選手、內層跑天,每一天讀三個數。

圖 1 是範例 2 的表:每天的最高、最低要直的比一整欄;進步是橫的,和同一列的前一格比。

圖 1:範例 2 的日積分表,一列是一位選手、一欄是一天。第 1 天那一欄直的比:選手 2 的 33 最高,加 6 分;選手 4 的 13 最低,扣 3 分。選手 3 那一列橫的比:第 2 天的 27 大於第 1 天的 16、第 3 天的 30 大於 27,各加 5 分

每滿 10 分鐘:先除再乘。分鐘數除以 \(10\) 是整數除法,小數丟掉、只留商(語法書 2.6),正好是「滿幾次 \(10\) 分鐘」,再乘上分數:walk / 10 * x。順序不能反過來:* 和 / 由左往右算,walk * x / 10 先把零頭的分鐘也乘上了分數才除。範例 1 選手 \(1\) 第 \(1\) 天步行 \(25\) 分鐘、\(X = 2\):25 / 10 * 2 是 \(4\),25 * 2 / 10 卻是 \(5\)。

一天一天加分扣分。第 \(d\) 天:

  • 每位選手先加上自己的日積分。
  • 從第 \(2\) 天起,日積分大於自己前一天的再加 \(S\):d >= 2 && daily[i][d] > daily[i][d - 1]。比的是日積分本身;和前一天一樣不算進步(範例 2 的選手 \(2\))。d >= 2 不能漏:第 \(1\) 天會拿 daily[i][0] 來比,全域陣列沒填過的格子是 \(0\),範例 1 就會印成 2 59。
  • 只有兩個人:日積分高的加 \(A\)、低的扣 \(B\)。題目保證同一天的日積分不一樣,不會平手。

最後兩個人比總積分,大的就是答案。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;
const int MAX_K = 20;

int daily[MAX_N + 1][MAX_K + 1];   // daily[i][d]:選手 i 第 d 天的日積分(都從 1 用起)
int total[MAX_N + 1];              // total[i]:選手 i 的總積分

int main() {
    int n, k;
    cin >> n >> k;
    int x, y, z, a, b, s;
    cin >> x >> y >> z >> a >> b >> s;
    for (int i = 1; i <= n; i++) {                 // 輸入的一行是一位選手
        for (int d = 1; d <= k; d++) {             // 每 3 個數是一天
            int walk, run, bike;
            cin >> walk >> run >> bike;
            daily[i][d] = walk / 10 * x + run / 10 * y + bike / 10 * z;   // 先除再乘:滿幾次 10 分鐘
        }
    }

    for (int d = 1; d <= k; d++) {
        for (int i = 1; i <= n; i++) {
            total[i] += daily[i][d];
            if (d >= 2 && daily[i][d] > daily[i][d - 1]) total[i] += s;   // 第 2 天起,比前一天大才加
        }
        if (daily[1][d] > daily[2][d]) {           // 子題組 1 保證 n = 2:兩個人直接比
            total[1] += a;
            total[2] -= b;
        } else {
            total[2] += a;
            total[1] -= b;
        }
    }

    if (total[1] > total[2]) cout << 1 << ' ' << total[1] << '\n';
    else cout << 2 << ' ' << total[2] << '\n';
    return 0;
}

範例 2 有 \(4\) 位選手,這份程式交上去範例 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手;想自己驗,用範例 1 和自測表的第 1~4 列(都是 \(N = 2\))。

從 60 分到 100 分:每天打兩次擂台,最後再打一次

\(N\) 位選手時,「當天最高」「當天最低」「總積分最高」都要從 \(N\) 個人裡挑出來,三個都用擂台(語法書 4.10),而且都讓選手 \(1\) 先上台、選手 \(2\)~\(N\) 輪流挑戰:

  • 每一天:選手 \(1\) 同時是目前最高和目前最低;挑戰者比最高的大就換最高、比最低的小就換最低。
  • 最後找第一名:挑戰者的總積分比台上的大才換。不能讓 \(0\) 先上台:總積分可能是負的——日積分很少、又常被扣 \(B\) 分的話,所有人都可能是負分(自測表第 3 列兩個人都是負分)。
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;
const int MAX_K = 20;

int daily[MAX_N + 1][MAX_K + 1];   // daily[i][d]:選手 i 第 d 天的日積分(都從 1 用起)
int total[MAX_N + 1];              // total[i]:選手 i 的總積分

int main() {
    int n, k;
    cin >> n >> k;
    int x, y, z, a, b, s;
    cin >> x >> y >> z >> a >> b >> s;
    for (int i = 1; i <= n; i++) {                 // 輸入的一行是一位選手
        for (int d = 1; d <= k; d++) {             // 每 3 個數是一天
            int walk, run, bike;
            cin >> walk >> run >> bike;
            daily[i][d] = walk / 10 * x + run / 10 * y + bike / 10 * z;   // 先除再乘:滿幾次 10 分鐘
        }
    }

    for (int d = 1; d <= k; d++) {
        for (int i = 1; i <= n; i++) {
            total[i] += daily[i][d];
            if (d >= 2 && daily[i][d] > daily[i][d - 1]) total[i] += s;   // 第 2 天起,比前一天大才加
        }
        int hi = 1, lo = 1;                        // 選手 1 先上台:同時是目前最高、目前最低
        for (int i = 2; i <= n; i++) {             // 選手 2~n 輪流挑戰
            if (daily[i][d] > daily[hi][d]) hi = i;
            if (daily[i][d] < daily[lo][d]) lo = i;
        }
        total[hi] += a;
        total[lo] -= b;
    }

    int best = 1;                                  // 選手 1 先上台:總積分可能是負的,不能從 0 開始
    for (int i = 2; i <= n; i++)
        if (total[i] > total[best]) best = i;
    cout << best << ' ' << total[best] << '\n';
    return 0;
}

跟子題組版比,換掉的只有兩處:每天的「兩個人直接比」、最後的「兩個人比總積分」,都換成擂台。表格最多 \(20 \times 20 = 400\) 格,時間完全不是問題;日積分最多 \(12 \times 10 \times 3 = 360\),總積分在 \(-10 \times 20 = -200\) 與 \(360 \times 20 + 10 \times 20 + 10 \times 19 = 7590\) 之間,int 綽綽有餘(語法書 2.9)。

測過再交:範例 1 沒有和前一天一樣的日積分,第一名也都是正分

範例的分鐘數已經有零頭(像 25、19),也考到第 \(1\) 天不比進步、和前一天一樣不算進步(範例 2)。可是子題組版只能用範例 1,它沒有和前一天一樣的日積分;兩個範例的第一名都是正分,日積分也都不到 \(40\);把當天的加分扣分算進去再比進步,兩個範例的答案也不會變。自己補上這幾種:

輸入 正確輸出 這一筆在測什麼
2 2 / 1 1 1 1 1 1 / 30 0 0 19 19 10 / 10 0 0 20 0 0 1 8 選手 \(1\) 第 \(2\) 天的 \(19\)、\(19\)、\(10\) 分鐘各只滿 \(1\) 次 \(10\) 分鐘,兩天的日積分都是 \(3\),不算進步
2 2 / 1 1 1 1 1 2 / 20 0 0 30 0 0 / 0 0 0 40 0 0 1 7 選手 \(1\) 第 \(2\) 天的日積分 \(3\) 比第 \(1\) 天的 \(2\) 大,要加 \(S\);他第 \(1\) 天最高、第 \(2\) 天最低,算上加分扣分反而變小
2 2 / 1 1 1 1 10 1 / 10 0 0 0 0 0 / 0 0 0 10 0 0 2 -7 兩個人都是負分:每天都是 \(1\) 分對 \(0\) 分,低的扣 \(10\) 分
2 2 / 10 10 10 10 10 1 / 120 120 120 0 0 0 / 120 120 110 20 0 0 2 370 第 \(1\) 天兩個人的日積分是 \(360\)(最大值)和 \(350\),都在 \(300\) 以上
3 2 / 1 1 1 1 10 1 / 0 0 0 10 0 0 / 20 0 0 0 0 0 / 10 0 0 20 0 0 3 5 三個人:第 \(1\) 天選手 \(1\) 最低(\(0\) 分)、選手 \(2\) 最高,選手 \(3\) 在中間

五筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 進步寫成 >=:範例 2 抓得到;子題組版只能用範例 1,要靠自測表第 1 列,印 1 9。
  • 拿加過分的分數比進步(日積分加上當天的加分扣分,再和前一天的同一個數比):兩個範例都過,自測表第 2 列印 2 6。
  • 最高、最低改用 \(-1\) 和很大的數當初值、從選手 \(1\) 開始比,卻寫成 if … else if:選手 \(1\) 一定先進「最高」那一支,他是當天最低時就被漏掉——兩個範例都過,自測表第 5 列印 1 2。
  • 最低的初值不夠大:寫成 \(0\),日積分都不小於 \(0\),沒有人比它小,範例 1 就印 2 58;要比日積分的最大值 \(360\) 還大,寫成 \(300\) 的話兩個範例都過,自測表第 4 列印 2 380。
  • 找第一名時讓 \(0\) 先上台:兩個範例都過,自測表第 3 列印 0 0。