メモ

自分に向けて書いたメモを取り扱っています.

SRM 403 TheLuckyNumbers

問題概要

サンプルセット見れば分かる.
aとbが与えられる.
4と7で構成されている数の内, [a, b]に存在する数を求める

方針

再帰で4と7をつなぎ合わせていったら解けると予想.
引数にstringを持ってくる.
b a d _ a l l o c

素直に整数で実装すると通ります.
ただし, 引数のlong longをintにすると最大ケースの時, 死にます

class TheLuckyNumbers
{
    int res;

    void dfs(long long x, int& a, int &b)
    {
        if(x > b)
            return;

        if(a <= x && x <= b)
            res++;

        dfs(x * 10 + 4, a, b);
        dfs(x * 10 + 7, a, b);

        return;
    }

    public:

    int count(int a, int b)
    {
        dfs(4, a, b);
        dfs(7, a, b);

        return res;
    }
};