d132 - 00340 - Master-Mind Hints
題目描述
題目描述了 Master-Mind 遊戲，要求模擬出題者的行為，針對解題者的每次猜測，計算並輸出 A (位置和數字都正確) 和 B (數字正確但位置錯誤) 的數量。
解題思路
程式碼直接模擬了 Master-Mind 遊戲的規則。首先讀取密碼，然後進入迴圈讀取猜測。對於每次猜測，程式碼首先計算 A 的數量，即位置和數字都相同的數字個數。然後計算 B 的數量，即數字相同但位置不同的數字個數。計算 B 的數量時，需要注意每個密碼數字和猜測數字最多只能配對一次。程式碼使用 used 陣列來記錄密碼數字是否已被配對。
複雜度分析
- 時間複雜度: O(n^2 * g)，其中 n 是密碼長度，g 是猜測次數。因為對於每次猜測，需要遍歷密碼和猜測陣列來計算 A 和 B 的數量。
- 空間複雜度: O(n)，主要用於儲存密碼、猜測和
used陣列。
程式碼
#include <iostream>
using namespace std;
int ans[1005],n,a[1005],ca;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
for(int i=0;i<n;++i){
cin >> ans[i];
}
cout << "Game " << ++ca << ":\n";
while(1){
int t=0;
for(int i=0;i<n;++i){
cin >> a[i];
if(a[i])t=1;
}
if(t==0)break;
int used[1005]={0},aa=0,bb=0;
for(int i=0;i<n;++i){
if(ans[i]==a[i]){
used[i]=1;
a[i]=-1;
++aa;
}
}
for(int i=0;i<n;++i){
if(a[i]!=-1){
for(int j=0;j<n;++j){
if(used[j]==0&&a[i]==ans[j]){
used[j]=1;
++bb;
j=n;
}
}
}
}
cout << " (" << aa << "," << bb << ")\n";
}
}
}