//全ての順列を試す -> QLE //「質問→回答」から、答えになり得ない順列が見つかる、それを除外することで「答えの候補となる順列」を高速に絞りこむ。 //値の重複が禁止されているので、3桁を固定して1桁だけ動かすことができない。そのため、1桁ずつ確定させていくことができない。 //よって、質問の順番は、適当にする。順番通りでQLEなら、適当にランダム… #include #include #include using namespace std; int permNum = 0; int perms[6000][4]; bool isNg[6000] = {false}; bool used[10] = {false}; int perm[10]; void setPerm(int dep) { if (dep == 4) { for (int i = 0; i < 4; i++) { perms[permNum][i] = perm[i]; } permNum++; return; } for (int i = 0; i < 10; i++) { if (used[i]) continue; used[i] = true; perm[dep] = i; setPerm(dep + 1); used[i] = false; } } pair query(int id) { cout << perms[id][0]; for (int i = 1; i < 4; i++) { cout << " " << perms[id][i]; } cout << endl; cout.flush(); int x, y; cin >> x >> y; return pair(x, y); } pair getHb(int id1, int id2) { int hit = 0; int blow = 0; int i, j; for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { if (perms[id1][i] == perms[id2][j]) break; } if (i == j) hit++; else if (j < 4) blow++; } return pair(hit, blow); } int main() { int i, j; setPerm(0); for (i = 0; i < permNum; i++) { if (isNg[i]) continue; pair hb = query(i); if (hb.first == 4) { break; } for (j = 0; j < permNum; j++) { if ( getHb(i, j) != hb ) { isNg[j] = true; } } } return 0; }