h082. 2. 贏家預測 - 高中生程式解題系統

內容

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

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

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

以上除法皆為無條件捨去

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

輸入說明

第一行輸入兩個正整數 $n$ 和 $m$ ，接下來一行有 $n$ 個正整數代表每個人分別的戰力值，接下來一行有 $n$ 個正整數代表每個人分別的應變力值，最後一行有 $n$ 個正整數代表第一 round 的初始排列順序。計算過程中 $a b$ 相乘的數值可能超過 $2^{32}$ ，但保證數值不超過 $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%): 無額外限制

輸出說明

輸出最終贏家的編號。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

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

標籤:

APCS 模擬陣列

出處:

2022年1月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
39972	aazz1415263@ ... (拉茲)	h082	different	428	2024-04-16 11:20
34513	willy633526@ ... (ByTech)	h082	python 題解	856	2023-03-26 22:29
34423	luray0601@gm ... (QWERTYPIG)	h082	C++題解	1247	2023-03-17 22:37
33210	a110608@ctes ... (鍾均)	h082	三種程式語言(C,C++,Python)簡單易懂的解題筆記(附完整解說&程式碼)	1604	2022-12-11 14:43
31561	a302854888@g ... (小麥)	h082	遞迴解	1079	2022-08-07 14:20