Solução Informática Intermediário - Semana 50 - Problema 2

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));
	}
	}

view raw

noic-s50-intermed-p2.cpp

hosted with ❤ by GitHub