1122-What is the Number in my Mind ?
問題概要
L個のそれぞれ異なる数字(0〜9)を用いた数に対してヒットアンドブローを行う。
h個の数に対するヒット数とブロー数が与えられるので、元の数が一意に復元できるかを調べろ。
一意に求められる場合はその数を求めよ。
考え方
DFSで数字を確定させていく。
このとき、ヒット数とブロー数と外れた数はそれぞれ増えるだけなので、
入力のヒット数、ブロー数、外れた数を越えたものを枝刈りする。
/*時間制限がなかったらnext_permutation安定だと思う*/
実装(C++)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <vector> using namespace std; struct data{ int blow,hit; vector<int> val; vector<int> has; }; istream &operator>>(istream &is,data &a){ string t; is>>t>>a.hit>>a.blow; a.val=vector<int>(t.size()); a.has=vector<int>(10); for(int i=0;i<t.size();i++){ a.val[i]=t[i]-'0'; a.has[t[i]-'0']=1; } return is; } ostream &operator<<(ostream &os,vector<int> &v){ for(int i=0;i<v.size();i++){ os<<v[i]; } return os; } int L,h; vector<int> val; vector<int> ans; int res; vector<data> datas; bool used[10]; inline bool check(int x){ for(int i=0;i<h;i++){ int blow=0,hit=0; for(int j=0;j<x;j++){ if(datas[i].val[j]==val[j])hit++; blow+=datas[i].has[val[j]]; } if(datas[i].hit<hit)return false; if(datas[i].blow<blow-hit)return false; if(L-datas[i].hit-datas[i].blow<x-blow)return false; } return true; } void solve(int x){ if(!check(x))return; if(x==L){ ans=val;res++; return; } for(int i=0;i<10;i++){ if(used[i]==false){ used[i]=true; val[x]=i; solve(x+1); if(res>1)return; used[i]=false; } } } int main(){ for(;cin>>L>>h;){ if(L==0&&h==0)break; val=vector<int>(L); datas=vector<data>(h); for(int i=0;i<h;i++){ cin>>datas[i]; } res=0; memset(used,0,sizeof(used)); solve(0); if(res==1){ cout<<ans<<endl; }else{ cout<<"NO"<<endl; } } }