#include using namespace std; static const int M = 30; struct Resp { array h; array b; }; static inline string digits_to_string(const array& a){ string s; s.reserve(5); for(int i=0;i<5;i++) s.push_back(char('0'+a[i])); return s; } static Resp ask(const string& q){ cout << q << "\n"; cout.flush(); // flush必須 :contentReference[oaicite:12]{index=12} Resp r; for(int i=0;i> r.h[i] >> r.b[i])) { // 入力が途切れたら終了 exit(0); } } // 不正なやり取り (-1,-1) が返る場合がある :contentReference[oaicite:13]{index=13} if(r.h[0]==-1 && r.b[0]==-1) exit(0); // (H0,B0)=(5,0) なら全て当て終わり :contentReference[oaicite:14]{index=14} if(r.h[0]==5) exit(0); return r; } // そのクエリで「数字集合が完全一致しているが未解決」な秘密の個数 // = (h+b==5 かつ h!=5) の本数 static int count_sum5_nonhit(const Resp& r){ int c=0; for(int i=0;i& a, const array& g){ int h=0; for(int i=0;i<5;i++) if(a[i]==g[i]) h++; return h; } // 候補集合 cand(配列の集合)の中から minimax で次の guess を選ぶ static array choose_minimax_guess(const vector>& cand){ // 返答 h は 0,1,2,3,5(4は起こらない)を想定 // h=5 は当たりなので worst-case の評価から除外してよい int bestWorst = INT_MAX; array best = cand[0]; for(const auto& g : cand){ int cnt[6] = {0,0,0,0,0,0}; for(const auto& a : cand){ int h = fixed_points(a,g); // h==4 は起こらない(4固定点なら残りも一致して5になる) cnt[h]++; } int worst = max({cnt[0], cnt[1], cnt[2], cnt[3]}); if(worst < bestWorst){ bestWorst = worst; best = g; } } return best; } // ブロック D(5種類の数字)に属する未解決秘密が「ちょうど1個」のとき、最悪6手でそれを当てる static void solve_unique_block(const array& D){ // 候補:D の全 5! = 120 通り array p = D; vector> cand; sort(p.begin(), p.end()); do { cand.push_back(p); } while(next_permutation(p.begin(), p.end())); while(true){ array g = choose_minimax_guess(cand); string q = digits_to_string(g); Resp r = ask(q); int h = read_h_for_unique_secret_in_block(r); if(h==5){ // 当たった return; } if(h<0){ // 想定外(ブロック内が1個じゃない等) return; } // 候補を絞る vector> nxt; nxt.reserve(cand.size()); for(const auto& a : cand){ if(fixed_points(a,g)==h) nxt.push_back(a); } cand.swap(nxt); } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // 252 個の数字集合(0..9 から 5 個選ぶ) vector> blocks; blocks.reserve(252); for(int a=0;a<10;a++) for(int b=a+1;b<10;b++) for(int c=b+1;c<10;c++) for(int d=c+1;d<10;d++) for(int e=d+1;e<10;e++){ blocks.push_back({a,b,c,d,e}); } // 各ブロックに属する未解決秘密数((h+b=5, h!=5) 本数) vector blockCnt(blocks.size(), -1); bool firstHitAccelerated = false; // まず 252 ブロックを1回ずつスキャンする(ここで count==1 が出たら即 solve して“最初の当たり”を早める) for(size_t i=0;i=2 のブロックは 120 通り総当たりで1個当てて count を減らし、最後1個になったら minimax for(size_t i=0;i 0){ if(blockCnt[i]==1){ solve_unique_block(blocks[i]); blockCnt[i] = 0; continue; } // count>=2:120通りを総当たりして1個当てに行く array p = blocks[i]; sort(p.begin(), p.end()); bool reduced = false; do { Resp r = ask(digits_to_string(p)); int newc = count_sum5_nonhit(r); if(newc < blockCnt[i]){ blockCnt[i] = newc; reduced = true; break; // 1個当たった(or とにかく減った)ので抜ける } } while(next_permutation(p.begin(), p.end())); if(!reduced){ // 120通りやっても減らないのはあり得ないが、安全のため抜ける break; } } } return 0; }