PKU : 3340 - Barbara Bennett's Wild Numbers
問題概要
http://poj.org/problem?id=3340
自然数Aと自然数Bが入力されます.
ただし, 自然数Aのどこかのケタは, '?'で隠されている可能性があります.
このとき, Bより大きくなるようなAは, いくつ作れるでしょう.
アルゴリズム
あるケタより上が等しいか等しくないかで分岐して, DFSしました.
もっと簡単な書き方があるかもしれないです.
プログラム
ll ans; int n; string a,b; void dfs(int idx,bool eq,ll mul){ if(idx == n){ if(!eq) ans += mul; return; } if(eq){ if(a[idx] == '?'){ if(b[idx] != '9') dfs(idx+1,false,mul*(ll)('9'-b[idx])); dfs(idx+1,true,mul); } else{ if(a[idx] < b[idx]) return; if(a[idx] == b[idx]) dfs(idx+1,true,mul); else dfs(idx+1,false,mul); } } else{ if(a[idx] != '?'){ dfs(idx+1,false,mul); } else{ dfs(idx+1,false,mul*10LL); } } } int main(void){ while(cin>>a,a!="#"){ cin>>b; n = a.length(); ans = 0; dfs(0,true,1); cout<<ans<<endl; } }