#include using namespace std; using pii=pair; using tii=tuple; using qii=tuple; using ll=long long; using ull=unsigned long long; using ld=long double; constexpr int INF=1e9; constexpr ll INF_ll=1e18; #define rep(i,n) for (int i=0;i<(int)(n);i++) #define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++) #define all(v) v.begin(),v.end() #define len(v) ((int)v.size()) template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a(now-start).count(); return ms; } int get_ms_all_program(){ auto now=chrono::system_clock::now(); int ms=chrono::duration_cast(now-program_start).count(); return ms; } } mt19937 mt; uint32_t rand_int(uint32_t r){ //[0,r) assert(r!=0); return ((uint64_t)mt()*r)>>32; } int rand_int(int l,int r){ //[l,r) assert(l T get_random_element(const vector &v){ assert(!v.empty()); return v[rand_int(len(v))]; } template void add(vector &a,vector b){ for(auto i:b) a.push_back(i); } constexpr int N=30,K=5,SZ=30240; vector C; int get_hb(int x_idx,int y_idx){ //TODOかも const string &x=C[x_idx]; const string &y=C[y_idx]; int h=0,b=0; rep(k,K){ if(x[k]==y[k]) h++; } rep(k,K){ rep(l,K){ if(k==l) continue; if(x[k]==y[l]) b++; } } return h*6+b; } namespace Communication{ vector S; vector finished; void init(){ S.resize(N); finished.resize(N,false); auto c=C; shuffle(all(c),mt); rep(i,N){ S[i]=c[i]; cerr << "ans:" << S[i] << '\n'; } cerr << '\n'; } int turn=0,finished_cnt=0; vector query(int q_idx){ string q=C[q_idx]; turn++; assert(len(q)==K); vector ret(N); #ifdef LOCAL rep(i,N){ if(S[i]==q||finished[i]){ ret[i]={5,0}; if(!finished[i]) finished_cnt++; finished[i]=true; continue; } int h=0,b=0; rep(k,K){ if(S[i][k]==q[k]) h++; } rep(k,K){ rep(l,K){ if(k==l) continue; if(S[i][k]==q[l]) b++; } } ret[i]={h,b}; } sort(all(ret)); #else cout << q << '\n'; cout.flush(); finished_cnt=0; rep(i,N){ int h,b; cin >> h >> b; if(h==K&&b==0) finished_cnt++; ret[i]={h,b}; } #endif if(ret.front()==pii{K,0}){ cerr << "turn:" << turn << '\n'; exit(0); } if(ret.front()==pii{-1,-1}) assert(0); return ret; } }; struct History{ int q; int hb; vector idxs; int now_cnt,true_cnt; }; namespace Solver{ vector historys; void solve(){ vector is_s(SZ,-1); //-1:不明 0:No 1:Yes vector accepting_idx,accepted_idx; int pre_ac=0; vector> idx_history(SZ); //[i]=set_cnt_historysに入っているインデックスの集合 while(true){ int q_idx=-1; if(!accepting_idx.empty()){ q_idx=accepting_idx.back(); accepting_idx.pop_back(); }else{ double best_score=-INF; rep(i,SZ){ if(is_s[i]!=-1) continue; double score=0; for(auto j:idx_history[i]){ const auto &[q,hb,idxs,now_cnt,true_cnt]=historys[j]; if(now_cnt!=true_cnt){ score+=(double)(true_cnt-now_cnt)/(double)(len(idxs)-now_cnt); } } if(chmax(best_score,score)) q_idx=i; } } if(q_idx==-1) break; vector hbs=Communication::query(q_idx); vector hb_cnt(36,0); int now_ac=0; for(auto [h,b]:hbs){ if(h==K){ now_ac++; continue; } hb_cnt[h*6+b]++; } if(pre_ac!=now_ac){ cerr << "ok:" << C[q_idx] << endl; is_s[q_idx]=1; accepted_idx.push_back(q_idx); }else{ is_s[q_idx]=0; } pre_ac=now_ac; for(auto i:accepted_idx){ hb_cnt[get_hb(q_idx,i)]++; } vector new_c; vector> hb_set(36); rep(i,SZ){ int hb=get_hb(q_idx,i); hb_set[hb].push_back(i); } rep(hb,36){ for(auto i:hb_set[hb]){ idx_history[i].push_back(len(historys)); } historys.emplace_back(q_idx,hb,hb_set[hb],0,hb_cnt[hb]); } while(true){ bool finish=true; for(auto &[q,hb,idxs,now_cnt,true_cnt]:historys){ //if(true_cnt==now_cnt) continue; int in_cnt=0,unknown_cnt=0; for(auto i:idxs){ if(is_s[i]==-1) unknown_cnt++; if(is_s[i]==1) in_cnt++; } assert(in_cnt<=true_cnt); if(in_cnt==true_cnt){ for(auto i:idxs){ if(is_s[i]==-1){ is_s[i]=0; finish=false; } } }else if(true_cnt-in_cnt==unknown_cnt){ for(auto i:idxs){ if(is_s[i]==-1){ cerr << "ok2:" << C[i] << endl; is_s[i]=1; accepting_idx.push_back(i); finish=false; } } } now_cnt=in_cnt; } if(finish) break; } } assert(0); } } void init(){ rep(i,100000){ string s=to_string(i); while(len(s)