h082: 2. 贏家預測
Tags : APCS 模擬 陣列
Accepted rate : 282人/355人 ( 79% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-01-09 19:53

Content

有 $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,直到僅剩一個人成為最終勝利者,並輸出他的編號。

Input

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

輸出最終贏家的編號。

Sample Input #1
4 1
4 2 5 3
2 5 1 5
1 2 3 4
Sample Output #1
4
Sample Input #2
4 5
4 1 5 3
6 5 1 6
4 1 3 2
Sample Output #2
1
測資資訊:
記憶體限制: 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
Hint :

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

Tags:
APCS 模擬 陣列
出處:
2022年1月APCS [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
30140
wubaie (小億)
h082
77 2022-05-01 14:12