# APCS實作題2024年1月第1題：遊戲選角

> 日期：2024年1月29日
> 作者：王一哲
> 題目來源：2024年1月實作題第1題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m931)

## 題目

### 問題描述

有 $n$ 個角色，每個角色有攻擊力和防禦力。
角色的能力值是攻擊力和防禦力的平方和，輸出能力值第二大的攻擊力和防禦力數值。
保證每個角色的能力值相異。
<br />

### 輸入說明

第一行包含一個整數 $n (3 \leq n \leq 20)$，表示有多少個角色。

接下來的 $n$ 行，每行包含兩個整數 $a_i$ 和 $d_i$，表示第 $i$ 個角色的攻擊力和防禦力。

子題分數：
- 60%：滿足 $n=3$。
- 40%：一般情況。
<br />

### 輸出格式

輸出兩個整數，表示能力值第二大的角色的攻擊力和防禦力。
<br />

### 範例輸入1

3
3 1
5 2
1 4

### 範例輸出1

1 4

<br />

### 範例輸入2

6
6 6
1 3
8 6
5 4
2 8
7 2

### 範例輸出2

6 6

<br />

### 範例輸入3

5
34 35
84 32
39 79
59 89
59 31

### 範例輸出3

84 32

<br />

## Python 程式碼

### 方法1，暴力解，計算每一項的平方和再由大到小排序

因為每一筆測資最多只有20項，暴力解也不會超時。費時約為 27 ms，使用記憶體約為 3.3 MB，通過測試。

n = int(input())  # 讀取角色人數 n
# 讀取接下來 n 行的角色數值，轉成整數存入串列 data，第4、5行有一樣的效果
data = [list(map(int, input().split())) for i in range(n)]
#for i in range(n):
#    data.append(list(map(int, input().split())))
# 計算每個角色的能力值平方和，再由大到小排序
data.sort(reverse=True, key=lambda x : x[0]*x[0] + x[1]*x[1])
print("{:d} {:d}".format(data[1][0], data[1][1]))  # 印出答案

<br />

### 方法2，計算每一項的平方和，記錄目前最大的兩個值

速度沒有比暴力解快。費時約為 31 ms，使用記憶體約為 3.3 MB，通過測試。

n = int(input())  # 讀取角色人數 n
# 讀取接下來 n 行的角色數值，轉成整數存入串列 data
data = [list(map(int, input().split())) for i in range(n)]
first, second = [-1, -1], [-1, -1]  # 目前最大的兩個值，內容為 [能力值, 索引值]
for i, d in enumerate(data):  # 依序讀取 data 的資料
    val = d[0]*d[0] + d[1]*d[1]  # 計算能力值平方和 val
    if val >= first[0]:  # 如果 val 大於 first[0]
        second = first   # second 更新為目前的 first
        first = [val, i] # first 更新為 [val, i]
    elif val >= second[0]:  # 如果 val 小於 first[0]、大於 second[0]
        second = [val, i]   # second 更新為 [val, i]
print("{:d} {:d}".format(data[second[1]][0], data[second[1]][1]))  # 印出答案

<br />

## C++ 程式碼

### 方法1，暴力解，計算每一項的平方和再由大到小排序

因為每一筆測資最多只有20項，暴力解也不會超時。費時約為 2 ms，使用記憶體約為 324 kB，通過測試。

#include <iostream>
#include <vector>
#include <utility>  // for pair
#include <algorithm>  // for sort
using namespace std;

int main() {
    int n; cin >> n;  // 讀取角色人數 n
    vector<pair<int, int>> data;  // 儲存角色能力值的 vector，內容為 pair
    for(int i=0; i<n; i++) {  // 讀取 n 個角色的資料
        int a, d; cin >> a >> d;  // 攻擊力存入 a，防禦力存入 d
        data.push_back({a, d});  // 將 {a, d} 加入 data
    }
    /* 使用 lambda function 作為比較式，由能力值平方和由大到小排序 */
    sort(data.begin(), data.end(), [](pair<int, int> x, pair<int, int> y) {
         return x.first*x.first + x.second*x.second > y.first*y.first + y.second*y.second;
    });
    cout << data[1].first << " " << data[1].second << "\n";  // 印出答案
    return 0;
}

<br />

### 方法2，計算每一項的平方和，記錄目前最大的兩個值

方法1使用了比較多奇特的工具，方法2只使用基本的工具解題。速度沒有比暴力解快。費時約為 2 ms，使用記憶體約為 328 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;  // 讀取角色人數 n
    int data[n][2];  // 儲存角色能力值的 array，內容為 {a, d}
    for(int i=0; i<n; i++) {  // 讀取 n 個角色的資料
        int a, d; cin >> a >> d;  // 攻擊力存入 a，防禦力存入 d
        data[i][0] = a;  // 將 {a, d} 存入 data
        data[i][1] = d;
    }
    int first[2] = {-1, -1}, second[2] = {-1, -1};  // 目前最大的兩個值，內容為 [能力值, 索引值]
    for(int i=0; i<n; i++) {  // 依序讀取 data 的資料
        int a = data[i][0], d = data[i][1];  // 攻擊力存入 a，防禦力存入 d
        int val = a*a + d*d;  // 計算能力值平方和
        if (val >= first[0]) {  // 如果 val 大於 first[0]
            second[0] = first[0];  // second 更新為目前的 first
            second[1] = first[1];
            first[0] = val;  // first 更新為 {val, i}
            first[1] = i;
        } else if (val >= second[0]) {  // 果 val 小於 first[0]、大於 second[0]
            second[0] = val;  // second 更新為 {val, i}
            second[1] = i;
        }
    }
    cout << data[second[1]][0] << " " << data[second[1]][1] << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`