問題
http://community.topcoder.com/stat?c=problem_statement&pm=11461&rd=14439
解き方
４か７以外の数字は最大ひとつしか含めてはいけないので、
１つ含んでいる場合とひとつも含んでいない場合で場合分けすれば
すべての数字を発生させられる。
あとはa以上かつb以下か判定すればよい。
コード
class TheAlmostLuckyNumbersDivOne {
public:
int calc(long long x){
int ret=0;
while(x>0){
if(!(x%10==4||x%10==7))ret++;
x/=10;
}
return ret;
}
void dfs(long long x){
if(x<=b){
dfs(x*10+4);
dfs(x*10+7);
if(calc(x)==0){
for(int i=0;i<=9;i++){
if(i==0 && x==0)continue;
if(i==4 || i==7)continue;
dfs(x*10+i);
}
}
if(a<=x)ret++;
}
}
long long find(long long a_, long long b_) {
a=a_,b=b_;
ret=0;
dfs(0);
return ret;
}
};
public:
int calc(long long x){
int ret=0;
while(x>0){
if(!(x%10==4||x%10==7))ret++;
x/=10;
}
return ret;
}
void dfs(long long x){
if(x<=b){
dfs(x*10+4);
dfs(x*10+7);
if(calc(x)==0){
for(int i=0;i<=9;i++){
if(i==0 && x==0)continue;
if(i==4 || i==7)continue;
dfs(x*10+i);
}
}
if(a<=x)ret++;
}
}
long long find(long long a_, long long b_) {
a=a_,b=b_;
ret=0;
dfs(0);
return ret;
}
};