APCS202201 第2題贏家預測

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

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

每一場競賽的勝負判斷規則如下，假設第一個人的戰力為 a，應變力為b ，第二個人的戰力為c ，應變力為 d

1. 若 ab>=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，直到僅剩一個人成為最終勝利者，並輸出他的編號。

輸入說明

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

數字範圍

(1)2<=n<=1000 1<=m<=5

(2)1<=S[i],T[i]<=100

輸出說明

輸出最終贏家的編號。

輸入範例

4 1

4 2 5 3

2 5 1 5

1 2 3 4

4 5

4 1 5 3

6 5 1 6

4 1 3 2

輸出範例

提示：

範例輸入 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}

解題策略

模擬，使用陣列紀錄狀態，使用deque更新還存活的編號

Python程式碼(參考ChatGPT進行修改)