SRM510 Div1 Easy(250) TheAlmostLuckyNumbersDivOne

TheAlmostLuckyNumbersDivOne

16桁の全てのalmost lucky numberを生成して、a以上b以下かどうか調べる。10¹⁶はalmost luckyではない。

long long BT( int d, bool f, long long n, long long a, long long b )
{
    if ( d == 0 )
        return a<=n && n<=b ? 1 : 0;

    long long r = 0;

    for ( int i=0; i<10; i++ )
        if ( i==4 || i==7 || !f )
            r += BT( d-1, f || i!=0&&i!=4&&i!=7 || i==0&&n>0, 10*n+i, a, b );

    return r;   
}

class TheAlmostLuckyNumbersDivOne{public:
long long find( long long a, long long b )
{
    return BT( 16, false, 0, a, b );
}};