please could help me with the problem B. Undoubtedly Lucky Numbers using DFS and please excuse my English
please could help me with the problem B. Undoubtedly Lucky Numbers using DFS and please excuse my English
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
Name |
---|
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) {
if(cnt == 1) { if(y == 0) { m[cnt] = x;
f(cnt + 1, x, y); } else {
m[cnt] = x; f(cnt + 1, x, y);
}
}
}
}
int main () {
cout << st.size() << endl;
return 0;
}
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.