PKU 3340 Barbara Bennett's Wild Numbers
http://poj.org/problem?id=3340
同じ桁数の数字WとXが与えられる。
この時Wの桁のいくつかはわからないようになっている。
この条件のもとでWとして考えられる数字のうち、Xより大きいものの個数を求めろというような問題。
あまり得意じゃない問題。TopCoderとかで出たら、雰囲気だけで萎えます。
今回は桁が同じという条件があったので多少解きやすい気がしました。
ll ans; string a,b; void dfs(int pos,int lq){ if(pos==SZ(a)){ return; } if(a[pos]=='?'){ dfs(pos+1,lq-1); ll t=1; rep(i,lq-1)t*=10; ans+=('9'-b[pos])*t; return; } if(a[pos]<b[pos])return; if(a[pos]==b[pos]){ dfs(pos+1,lq); return; } ll t=1; rep(i,lq)t*=10; ans+=t; } main(){ while(cin>>a){ if(a=="#")break; cin>>b; int lq=0; ans=0; rep(i,SZ(a))lq+=a[i]=='?'; dfs(0,lq); cout<<ans<<endl; } }