問題
http://community.topcoder.com/stat?c=problem_statement&pm=8568&rd=12175
整数aとbが与えられる。
a以上かつb以下の整数のうち、4と7からなる整数の総数を求める。
解き方
a,bは10^9でありすべて全探索しては間に合わないが、
４と７からなる数字は2^9のため、
DFSにて４と７からなるすべての数字について調べればよい。
コード
int ret,a,b;
class TheLuckyNumbers {
public:
void dfs(long long x){
if(x<=b){
dfs(x*10+4);
dfs(x*10+7);
if(a<=x)ret++;
}
}
int count(int a_, int b_) {
a=a_,b=b_;
ret=0;
dfs(0);
return ret;
}
};
class TheLuckyNumbers {
public:
void dfs(long long x){
if(x<=b){
dfs(x*10+4);
dfs(x*10+7);
if(a<=x)ret++;
}
}
int count(int a_, int b_) {
a=a_,b=b_;
ret=0;
dfs(0);
return ret;
}
};