# APCS實作題2022年1月第2題：贏家預測

> 日期：2023年9月22日
> 作者：王一哲
> 題目來源：111年1月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h082)

<br />

## 題目

### 問題描述

有 $n$ 的人要比賽，每個人的戰力為 $S[1], S[2], \dots, S[n]$，而應變力為 $T[1], T[2], \dots, T[n]$，編號為 $1$ 到 $n$。

一開始將這 $n$ 個人按照編號為 $idx[1], idx[2], \dots, idx[n]$ 的順序排成一列，並從陣列前端開始兩兩一組進行配對競賽，若該 round 有奇數人數，則最後一個烙單的人直接晉級下一 round，並不獲得戰力和應變力數值的增加。

每一場競賽的勝負判斷規則如下，假設第一個人的戰力為 $a$，應變力為 $b$，第二個人的戰力為 $c$，應變力為 $d$。
1. 若 $ab \geq cd$ 則第一個人獲勝，並且勝利方（第一個人）的戰力變為 $a + cd/(2b)$，應變力變為 $b + cd/(2a)$，失敗方（第二個人）的戰力變為 $c + c/2$，應變力變為 $d + d/2$。
2. 若 $ab < cd$ 則第二個人獲勝，並且勝利方（第二個人）的戰力變為 $c + ab/(2d)$，應變力變為 $d + ab/(2c)$，失敗方（第一個人）的戰力變為 $a + a/2$，應變力變為 $b + b/2$。

以上除法皆為無條件捨去。

該 round 每組勝負揭曉後，按照原有順序將他們排列並分成勝利組和失敗組，失敗組中若有人已經輸了 $m$ 次則被淘汰，再將失敗組接在勝利組之後形成新的排列進行下一 round，直到僅剩一個人成為最終勝利者，並輸出他的編號。
<br />

### 輸入說明

第一行輸入兩個正整數 $n$ 和 $m$，接下來一行有 $n$ 個正整數代表每個人分別的戰力值，接下來一行有 $n$ 個正整數代表每個人分別的應變力值，最後一行有 $n$ 個正整數代表第一 round 的初始排列順序。計算過程中 $ab$ 相乘的數值可能超過 $2^{23}$，但保證數值不超過 $2^{60}$。

數字範圍
- $2 \leq n \leq 1000$, $1 \leq m \leq 5$
- $1 \leq S[i], T[i] \leq 100$

子題配分
- 50%：$2 \leq n \leq 100$, $m = 1$
- 50%：無額外限制

<br />

### 輸出說明

輸出最終贏家的編號。

<br />

### 範例一：輸入

4 1
4 2 5 3
2 5 1 5
1 2 3 4

### 範例一：正確輸出

4

<br />

### 範例二：輸入

4 5
4 1 5 3
6 5 1 6
4 1 3 2

### 範例二：正確輸出

1

<br />

## 提示

範例輸入 1
第 1 輪的編號為：{1, 2, 3, 4}, 戰力為：{4, 2, 5, 3}, 應變力為：{2, 5, 1, 5}, 失敗次數為：{1, 0, 1, 0}
第 2 輪的編號為：{2, 4}, 戰力為：{6, 2, 7, 3}, 應變力為：{3, 7, 1, 5}, 失敗次數為：{1, 1, 1, 0}

範例輸入 2
第 1 輪的編號為：{4, 1, 3, 2}, 戰力為：{4, 1, 5, 3}, 應變力為：{6, 5, 1, 6}, 失敗次數為：{0, 1, 0, 1}
第 2 輪的編號為：{1, 3, 4, 2}, 戰力為：{5, 1, 7, 4}, 應變力為：{8, 7, 1, 9}, 失敗次數為：{0, 2, 1, 1}
第 3 輪的編號為：{1, 4, 3, 2}, 戰力為：{5, 1, 10, 4}, 應變力為：{8, 10, 1, 9}, 失敗次數為：{0, 3, 1, 2}
第 4 輪的編號為：{1, 3, 4, 2}, 戰力為：{7, 1, 15, 6}, 應變力為：{11, 15, 1, 13}, 失敗次數為：{0, 4, 2, 2}
第 5 輪的編號為：{1, 4, 3, 2}, 戰力為：{7, 1, 22, 6}, 應變力為：{12, 22, 1, 14}, 失敗次數為：{0, 5, 2, 3}
第 6 輪的編號為：{1, 3, 4}, 戰力為：{10, 1, 33, 9}, 應變力為：{18, 33, 1, 21}, 失敗次數為：{0, 5, 3, 3}
第 7 輪的編號為：{1, 4, 3}, 戰力為：{10, 1, 49, 9}, 應變力為：{19, 33, 1, 21}, 失敗次數為：{0, 5, 3, 4}
第 8 輪的編號為：{1, 3, 4}, 戰力為：{14, 1, 49, 13}, 應變力為：{28, 33, 1, 31}, 失敗次數為：{0, 5, 4, 4}
第 9 輪的編號為：{1, 4, 3}, 戰力為：{14, 1, 73, 13}, 應變力為：{29, 33, 1, 31}, 失敗次數為：{0, 5, 4, 5}
第 10 輪的編號為：{1, 3}, 戰力為：{20, 1, 73, 19}, 應變力為：{43, 33, 1, 46}, 失敗次數為：{0, 5, 5, 5}

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 41 ms，使用記憶體最多約為 3.6 MB，通過測試。

n, m = map(int, input().split())     # 人數、失敗次數上限
S = list(map(int, input().split()))  # 戰力
T = list(map(int, input().split()))  # 應變力
Q = list(map(int, input().split()))  # 上場順序
M = [0]*n      # 每人失敗次數

while len(Q) > 1： # Q 長度大於1繼續執行
    #print("Q：", Q, " S：", S, "T：", T, end=" ")  # 除錯用
    W, L = [], []  # 贏家、輸家
    while Q： # Q 如果有內容繼續執行
        if len(Q) == 1： # 如果這輪只剩下1人
            W.append(Q.pop(0))  # 直接加到贏家名單
        else： # 如果這輪還有2人以上
            q1 = Q.pop(0)  # 取出 Q 最前面的人存入 q1
            q2 = Q.pop(0)  # 取出 Q 最前面的人存入 q2
            a, b, c, d =S[q1-1], T[q1-1], S[q2-1], T[q2-1]  # 取出兩人對應的戰力及應變力，分別存入a, b, c, d
            if a*b >= c*d： # 如果 q1 獲勝
                W.append(q1)  # 將 q1 加到贏家名單
                S[q1-1] = a + c*d//(2*b)  # 更新 q1 對應的戰力
                T[q1-1] = b + c*d//(2*a)  # 更新 q1 對應的應變力
                S[q2-1] = c + c//2  # 更新 q2 對應的戰力
                T[q2-1] = d + d//2  # 更新 q2 對應的應變力
                M[q2-1] += 1  # q2 對應的失敗次數加1
                if M[q2-1] < m：L.append(q2)  # 如果 q2 失敗次數小於 m，將 q2 加入輸家名單
            else： # 如果 q2 獲勝
                W.append(q2)  # 將 q2 加到贏家名單
                S[q1-1] = a + a//2  # 更新 q1 對應的戰力
                T[q1-1] = b + b//2  # 更新 q1 對應的應變力
                S[q2-1] = c + a*b//(2*d)  # 更新 q2 對應的戰力
                T[q2-1] = d + a*b//(2*c)  # 更新 q2 對應的應變力
                M[q1-1] += 1  # q1 對應的失敗次數加1
                if M[q1-1] < m：L.append(q1)  # 如果 q1 失敗次數小於 m，將 q1 加入輸家名單
    #print("M：", M)  # 除錯用
    Q = W + L  # 更新下一輪的名單
print(Q[0])  # 印出答案

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 4 ms，使用記憶體最多約為 360 kB，通過測試。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, m; cin >> n >> m;  // 人數、失敗次數上限
    unsigned long long S[n], T[n];     // 戰力、應變力
    int M[n] = {0};           // 每人失敗次數
    queue<int> Q;          // 上場順序
    for(int i=0; i<n; i++) cin >> S[i]; 
    for(int i=0; i<n; i++) cin >> T[i];
    for(int i=0; i<n; i++) {
        int tmp; cin >> tmp;
        Q.push(tmp);
    }

    while(Q.size() > 1) {  // Q 長度大於1繼續執行
        queue<int> W, L;  // 贏家、輸家
        while(!Q.empty()) {  // Q 如果有內容繼續執行
            if (Q.size() == 1) {  // 如果這輪只剩下1人
                W.push(Q.front());  // 直接加到贏家名單
                Q.pop();
            } else {  // 如果這輪還有2人以上
                int q1 = Q.front(); Q.pop();  // 取出 Q 最前面的人存入 q1
                int q2 = Q.front(); Q.pop();  // 取出 Q 最前面的人存入 q2
                unsigned long long a = S[q1-1], b = T[q1-1], c = S[q2-1], d = T[q2-1];  // 取出兩人對應的戰力及應變力，分別存入a, b, c, d
                if (a*b >= c*d) {  // 如果 q1 獲勝
                    W.push(q1);  // 將 q1 加到贏家名單
                    S[q1-1] = a + c*d/(2*b);  // 更新 q1 對應的戰力
                    T[q1-1] = b + c*d/(2*a);  // 更新 q1 對應的應變力
                    S[q2-1] = c + c/2;  // 更新 q2 對應的戰力
                    T[q2-1] = d + d/2;  // 更新 q2 對應的應變力
                    M[q2-1]++;  // q2 對應的失敗次數加1
                    if (M[q2-1] < m) L.push(q2);  // 如果 q2 失敗次數小於 m，將 q2 加入輸家名單
                } else {  // 如果 q2 獲勝
                    W.push(q2);  // 將 q2 加到贏家名單
                    S[q1-1] = a + a/2;  // 更新 q1 對應的戰力
                    T[q1-1] = b + b/2;  // 更新 q1 對應的應變力
                    S[q2-1] = c + a*b/(2*d);  // 更新 q2 對應的戰力
                    T[q2-1] = d + a*b/(2*c);  // 更新 q2 對應的應變力
                    M[q1-1]++;  // q1 對應的失敗次數加1
                    if (M[q1-1] < m) L.push(q1);  // 如果 q1 失敗次數小於 m，將 q1 加入輸家名單
                }
            }
        }
        /* 更新下一輪的名單 */
        while(!W.empty()) {
            Q.push(W.front()); W.pop();
        }
        while(!L.empty()) {
            Q.push(L.front()); L.pop();
        }
    }
    cout << Q.front() << endl;  // 印出答案
    return 0;
}

<br /><br />

---

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