Interactive Bulls and Cows - codeforces753
where
一直沒有好的想法，所以直接看別人的code（汗。
這次記起來，下次遇到如果又忘了可以回來看一下。:)
加油！
思考
由此證明可知，只要將不可能的一步步去除，即可在七步以內得出答案。
可能解：
輸出答案為X
若另一Y和X比得出的Bull和Cow等同於輸入給的
則為可能解
初始：
遞迴4個position
#include <bits/stdc++.h>
using namespace std;
vector<string> possi;
bool valid[10];
void gen(string s){ //產出0~9999之數字不重複的字串
int i, j;
if(s.length() == 4){
possi.push_back(s);
return;
}
for(i = 0; i < 10; i++){
if(!valid[i]){ //重複的跳掉
valid[i] = 1; //已選，則標為一
gen(s+(char)(i + '0'));
valid[i] = 0; //不選了，要回家了
}
}
}
bool check(string x, string y, int B, int C){
int i, b, c;
memset(valid, 0, sizeof(exist));
for(i = b = c = 0; i < 4; i++){
if(x[i] == y[i]) b++; //如果有在同個位置，則Bull++
valid[(x[i] - '0')] = 1; //出現->1
}
for(i = 0; i < 4; i++){
if(valid[(y[i] - '0')]) c++; //如果有出現同個數字，則Cow++
}
c -= b;
//因有出現同個數字會包含出現在同個位置，因此真正的C要減去Bull
return (b == B) && (c == C); //傳回B, C是否相同（為可能解）
}
int main(void){
int i, B, C;
gen("");
srand(2333333); //種子
while(1){
random_shuffle(possi.begin(), possi.end()); //洗牌
cout<<possi[0]<<endl;
fflush(stdout);
cin>>B>>C;
if(B == 4) return 0;
vector<string> temp;
for(i = 0; i < possi.size(); i++){
//每個測試是否為可能解，可能則丟到temp，再丟給possi
if(check(possi[0], possi[i], B, C))
temp.push_back(possi[i]);
}
possi = temp;
}
}