Блог пользователя DrPaulVazo

Автор DrPaulVazo, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.