How to solve this question with the help of dfs/bfs/dijktra(as mentioned in ahmed-aly.com).This particular question has not been discussed much and don't have good resources to know about it.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
How to solve this question with the help of dfs/bfs/dijktra(as mentioned in ahmed-aly.com).This particular question has not been discussed much and don't have good resources to know about it.
Name |
---|
I managed to solve this : Code
The main idea is to do a BFS, with the nodes being the pair(mod value , sum of digits).
Dude what made you come up with bfs ? Can you add comments in your code l'il bit :)
I can tell you how my code works. The start node is when the number is empty (0) with sum of digs and mod value is 0. We are doing the BFS since we need to find the minimum positive integer(which can be seen as shortest distance in the integer tree). Now if our element has a mod value 0 and sum of digits as N , then this is indeed our number and this is the shortest (since we are doing BFS , the first occurrence is indeed the smallest). Else what we try to do is append a digit [0-9] and mark this as a new node in the tree.
In code , the first two functions are basic ones. The bfs is also the basic one. I am using "lwr" variable to see if the digit can be 0 or not. This is done just to avoid leading zeroes.
You can ask if you have any doubts related to any part of code.