有 $n$ 的人要比賽，每個人的戰力為 $S_1, S_2, ..., S_n$，而應變力為 $T_1, T_2, ..., T_n$，編號為 $1$ 到 $n$。
一開始將這 $n$ 個人按照編號為 $\mathit{idx}_1, \mathit{idx}_2, ..., \mathit{idx}_n$ 的順序排成一列，並從陣列前端開始兩兩一組進行配對競賽，若該回合有奇數人數，則最後一個落單的人直接晉級下一回合，並不獲得戰力和應變力數值的增加。
每一場競賽的勝負判斷規則如下，假設第一個人的戰力為 $a$，應變力為 $b$，第二個人的戰力為 $c$，應變力為 $d$
1. 若 $a \times b \ge c \times d$ 則第一個人獲勝，並且勝利方 (第一個人) 的戰力變為 $a + \dfrac{cd}{2b}$，應變力變為 $b + \dfrac{cd}{2a}$，失敗方 (第二個人) 的戰力變為 $c + \dfrac{c}{2}$，應變力變為 $d + \dfrac{d}{2}$。
2. 若 $a \times b < c \times d$ 則第二個人獲勝，並且勝利方 (第二個人) 的戰力變為 $c + \dfrac{ab}{2d}$, 應變力變為 $d + \dfrac{ab}{2c}$，失敗方 (第一個人) 的戰力變為 $a + \dfrac{a}{2}$，應變力變為 $b + \dfrac{b}{2}$。
以上除法皆為無條件捨去
該回合每組勝負揭曉後，按照原有順序將他們排列並分成勝利組和失敗組。失敗組中若有人已經輸了 $m$ 次則被淘汰，再將失敗組接在勝利組之後形成新的排列進行下一回合，直到僅剩一個人成為最終勝利者，並輸出他的編號。
第一行輸入兩個正整數 $n$ 和 $m$，接下來一行有 $n$ 個正整數代表每個人分別的戰力值 $S_i$，接下來一行有 $n$ 個正整數代表每個人分別的應變力值 $T_i$，最後一行有 $n$ 個正整數代表第一回合的初始排列順序 $\mathit{idx}_i$。
計算過程中 $ab$ 相乘的數值可能超過 $2^{32}$，但保證數值不超過 $2^{60}$。
數字範圍
子題配分
輸出最終贏家的編號。
4 1 4 2 5 3 2 5 1 5 1 2 3 4
4
4 5 4 1 5 3 6 5 1 6 4 1 3 2
1
範例輸入 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}
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||