Solução por Lúcio Cardoso
Perceba que a situação do problema é equivalente a um grafo, onde cada número é um vértice. Neste grafo, cada número $$X$$ tem uma aresta para dois outros números: $$X+1$$ e o inverso de $$X$$ (número com digítos na ordem contrária na representação decimal).
Assim, o problema se resume em encontrar o menor caminho de um vértice $$A$$ para um vértice $$B$$ em um grafo com arestas simples (sem peso). Podemos resolver isto utilizando uma BFS (busca em profundidade), em $$O(N)$$, onde $$N$$ é o maior número presente no grafo.
Para descobrir o inverso de um certo número, iremos extrair todos os dígitos deste número na base 10. Depois, organizaremos estes dígitos em ordem inversa, multiplicando-os pelas respectivas potências de 10. A complexidade deste processo é $$O(\log_{10} N)$$ (ou seja, a quantidade de dígitos de um número $$N$$ na base 10).
A complexidade final será, portanto, $$O(N \cdot \log_{10} N)$$. Confira o código abaixo para melhor entendimento:
| // Noic – Semana 50 – Intermediário – Problema 2 | |
| // Complexidade: O(N * log_10 N) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 10010; | |
| int dist[maxn]; | |
| bool mark[maxn]; | |
| vector<int> grafo[maxn]; | |
| // inverso de um número x qualquer | |
| int inverso(int x) | |
| { | |
| // guardaremos os dígitos de x neste vetor | |
| vector<int> digits; | |
| while (x > 0) | |
| { | |
| int d = x%10; // o último dígito de x é x%10 | |
| x /= 10; // divimos x por 10 para encontrar os próximos dígitos | |
| digits.push_back(d); | |
| } | |
| // vamos percorrer os dígitos em ordem contrária | |
| reverse(digits.begin(), digits.end()); | |
| int y = 0; // resposta | |
| for (int i = 0; i < digits.size(); i++) | |
| { | |
| // multiplicamos cada dígito pela sua respectiva potência de 10 | |
| // (na ordem contrária de x) | |
| y += (pow(10, i)*digits[i]); | |
| } | |
| return y; | |
| } | |
| // menor distância de A para B | |
| int bfs(int a, int b) | |
| { | |
| queue<int> fila; | |
| fila.push(a); | |
| mark[a] = 1; // mark marca os vértices já visitados | |
| dist[a] = 0; | |
| while (!fila.empty()) | |
| { | |
| int x = fila.front(); | |
| fila.pop(); | |
| for (auto v: grafo[x]) | |
| { | |
| if (!mark[v]) | |
| { | |
| dist[v] = dist[x]+1, mark[v] = 1; | |
| fila.push(v); | |
| } | |
| } | |
| } | |
| return dist[b]-dist[a]; | |
| } | |
| int main(void) | |
| { | |
| int a, b, t; | |
| scanf("%d", &t); | |
| while (t–) | |
| { | |
| int a, b; | |
| scanf("%d %d", &a, &b); | |
| for (int i = 1; i <= 10000; i++) | |
| grafo[i].clear(); | |
| for (int i = 1; i <= 10000; i++) | |
| { | |
| // arestas do grafo | |
| grafo[i].push_back(i+1); | |
| grafo[i].push_back(inverso(i)); | |
| } | |
| memset(mark, 0, sizeof mark); | |
| printf("%d\n", bfs(a, b)); | |
| } | |
| } |

Comente