2022.12.11 AM 09:30 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=h082 出題者 : 2022年1月APCS 標籤 : 模擬、陣列 難易度 : 2
解題想法 : 根據題目定義進行實作即可,但須注意以下幾點 : 1. 兩兩配對時可能會有落單,需要另外判斷。 2. 由於題目會更改S[]和T[]的值,因此必須像題目敘述那樣複製給a,b,c,d再做計算。 3. 若以C/C++實作,記得開long long,Python除法記得用//。 4. 記得計算每個玩家的失敗次數,若大於等於m則不需進入下一輪。 實作上可以真的開一個winner[],一個loser[],存放贏家和輸家,最後再合併成為新的idx[],但要注意winner[]和loser[]清空&合併的時機。
//C language
#include<stdio.h>
int main(){
int n,m;
int S[1005], T[1005], idx[1005], times[1005]={0};
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&S[i]);
for(int i=0;i<n;i++) scanf("%d",&T[i]);
for(int i=0;i<n;i++) scanf("%d",&idx[i]);
int idx_size=n;
while(idx_size > 1){
int winner[505], loser[505];
int winner_size=0, loser_size=0;
for(int i=0;i<idx_size;i+=2){
int player1, player2;
if(i == idx_size - 1){
winner[winner_size++] = idx[i];
break;
}
else{
player1 = idx[i] - 1;
player2 = idx[i+1] - 1;
}
long long a=S[player1], b=T[player1],
c=S[player2], d=T[player2];
if(a*b >= c*d){
winner[winner_size++] = player1+1;
S[player1] = a+(c*d)/(2*b);
T[player1] = b+(c*d)/(2*a);
if(++times[player2] < m){
loser[loser_size++] = player2+1;
}
S[player2] = c+(c/2);
T[player2] = d+(d/2);
}
else{
winner[winner_size++] = player2+1;
S[player2] = c+(a*b)/(2*d);
T[player2] = d+(a*b)/(2*c);
if(++times[player1] < m){
loser[loser_size++] = player1+1;
}
S[player1] = a+(a/2);
T[player1] = b+(b/2);
}
}
idx_size=0;
for(int i=0;i<winner_size;i++){
idx[idx_size++] = winner[i];
}
for(int i=0;i<loser_size;i++){
idx[idx_size++] = loser[i];
}
}
printf("%d\n",idx[0]);
return 0;
}

//C++ language
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m,x;
cin>>n>>m;
vector<int>S(n+1,-1),T(n+1,-1),idx,times(n+1,0);
for(int i=1;i<=n;i++) cin>>S[i];
for(int i=1;i<=n;i++) cin>>T[i];
for(int i=0;i<n;i++) cin>>x, idx.push_back(x);
while(idx.size()>1){
vector<int>winner,loser;
for(int i=0;i<(int)idx.size();i+=2){
int player1,player2;
if(i+1 == idx.size()){
winner.push_back(idx[i]);
continue;
}
else{
player1=idx[i];
player2=idx[i+1];
}
long long a=S[player1], b=T[player1];
long long c=S[player2], d=T[player2];
if(a*b >= c*d){
winner.push_back(player1);
S[player1] = a + (c*d)/(2*b);
T[player1] = b + (c*d)/(2*a);
times[player2]++;
if(times[player2]<m)
loser.push_back(player2);
S[player2] = c + (c/2);
T[player2] = d + (d/2);
}
else{
winner.push_back(player2);
S[player2] = c + (a*b)/(2*d);
T[player2] = d + (a*b)/(2*c);
times[player1]++;
if(times[player1]<m)
loser.push_back(player1);
S[player1] = a + (a/2);
T[player1] = b + (b/2);
}
}
idx.clear();
for(int i:winner) idx.push_back(i);
for(int i:loser) idx.push_back(i);
}
cout<<idx[0]<<"\n";
return 0;
}

## Python language
n,m=map(int,input().split())
S=[-1]+[int(x) for x in input().split()]
T=[-1]+[int(x) for x in input().split()]
idx=[int(x) for x in input().split()]
times=[0]*(n+1)
while len(idx)>1:
winner=[]
loser=[]
for i in range(0,len(idx),2):
try:
player1,player2=idx[i],idx[i+1]
except IndexError:
winner.append(idx[i])
break
a,b,c,d=S[player1],T[player1],S[player2],T[player2]
if a*b>=c*d:
winner.append(player1)
S[player1] = a + (c*d)//(2*b)
T[player1] = b + (c*d)//(2*a)
times[player2]+=1
if times[player2]<m:
loser.append(player2)
S[player2] = c + (c//2)
T[player2] = d + (d//2)
else:
winner.append(player2)
S[player2] = c + (a*b)//(2*d)
T[player2] = d + (a*b)//(2*c)
times[player1]+=1
if times[player1]<m:
loser.append(player1)
S[player1] = a + (a//2)
T[player1] = b + (b//2)
idx=winner+loser
print(idx[0])
