有 $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 \ge 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}$。
數字範圍
子題配分
輸出最終贏家的編號。
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 |
39972 | aazz1415263@ ... (拉茲) | h082 | 275 | 2024-04-16 11:20 | |
34513 | willy633526@ ... (ByTech) | h082 | 675 | 2023-03-26 22:29 | |
34423 | luray0601@gm ... (QWERTYPIG) | h082 | 995 | 2023-03-17 22:37 | |
33210 | a110608@ctes ... (鍾均) | h082 | 1326 | 2022-12-11 14:43 | |
31561 | a302854888@g ... (小麥) | h082 | 993 | 2022-08-07 14:20 |