DrPaulVazo's blog

By DrPaulVazo, 12 years ago, In English

please could help me with the problem B. Undoubtedly Lucky Numbers using DFS and please excuse my English

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
12 years ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

using namespace std;

const int N = 123;

set st; ll n, m[20], c, sum, cdg, tt;

ll calc(int sz) {

ll ans = 0, res = 1; for (int j = sz; j >= 1; --j) { ans += res * m[j]; res *= 10; }

return ans; }

void f(int cnt, int x, int y) {

ll ans = 0, res = 1, q;
if(cnt > cdg) 
       return;


if(x == y) {
    m[cnt] = x;
    f(cnt + 1, x, y);             
} 

else {

if(cnt == 1) { if(y == 0) { m[cnt] = x;
f(cnt + 1, x, y); } else {
m[cnt] = x; f(cnt + 1, x, y);

q = calc(cnt);
if(q <= n) st.insert(q);

        m[cnt] = y;
        f(cnt + 1, x, y);

q = calc(cnt);
if(q <= n) st.insert(q);

}
}

else if(cnt > 1) {
    m[cnt] = x;
    f(cnt + 1, x, y);              

q = calc(cnt);
if(q <= n) st.insert(q);

    m[cnt] = y;
    f(cnt + 1, x, y);

q = calc(cnt);
if(q <= n) st.insert(q);

}

}

q = calc(cnt);
if(q <= n) st.insert(q);

}

int main () {

cin >> n; tt = n;

while (tt > 0) cdg ++, tt /= 10;


for (int i = 1; i <= 9; ++i) 
    for (int j = 0; j <= 9; ++j) { 
        f(1, i, j);
    }

cout << st.size() << endl;
return 0;

}

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The main idea is to brute force through all possible pairs of digits (i, j), i <= j. Then, for a specific digit-pair, you can run dfs, simply putting either i or j each time, until the number becomes too large. Depth is maximum 10, due to constraints, so theres only 2^10 calls. You can put every found solution into a set to avoid over-counting (counting the same element a few times). The complexity will be something like 2^10 * 50 * a logarithm of a not very large number.