Skip to Content
CTRL K

Small Multiple

Análisis oficial 

Explicación

Todos los enteros positivos se pueden crear partiendo de 1 y repitiendo las siguientes dos operaciones:

  1. Multiplicar el número actual por 10. En ese momento, la suma de cada dígito no cambia.
  2. Sumar 1 al número actual. En ese momento, la suma de cada dígito aumenta en 1. (Esto no aplica cuando el dígito de las unidades es 9, pero más adelante mostraremos que no hace falta tener esto en cuenta al resolver este problema.)

Ahora, consideremos un grafo con todos los enteros positivos como vértices y una arista desde el “número actual” hacia el “número nuevo” de la operación anterior. Lo que necesitamos hallar es la longitud del camino más corto en este grafo desde 1 hasta cualquier múltiplo de K, más 1.

Tal como está, la cantidad de vértices es infinita, pero si consideramos cómo se dibujan las aristas, se ve que los vértices correspondientes a cada entero positivo se pueden identificar con el módulo K.

Por lo tanto, solo necesitamos hallar el camino más corto de 1 a 0 en un grafo de K vértices, donde cada vértice se identifica con el módulo K, y esto se puede hallar en tiempo O(K) usando BFS 0-1 .

Una transición que suma 1 a un entero cuyo dígito de las unidades es 9 no necesita tratarse de forma especial, porque si recordamos el algoritmo de caminos más cortos, se ve que el vértice destino ya ha sido visitado. Por ejemplo, si vamos de 9 a 10 usando el segundo caso, no hay que preocuparse por el vértice 10, ya que ya habrá sido visitado desde el primer caso.

Notamos que el BFS 0-1 es un algoritmo de búsqueda en anchura que prepara un deque (cola de dos extremos) y agrega elementos al inicio del deque para transiciones de aristas con costo 0, y al final del deque para transiciones de aristas de costo 1.

Implementación

Complejidad temporal: O(K)\mathcal{O}(K)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
 
int main() {
	int k;
	scanf("%d", &k);
 
	// dist[i] = menor suma de dígitos para alcanzar i % k
	vector<int> dist(k, INF);
 
	deque<int> q;
 
	dist[1] = 1;
	q.push_front(1);
 
	while (!q.empty()) {
		int cur = q.front();
		q.pop_front();
 
		// caso 1: agregamos un 0 extra al final (SIN COSTO EXTRA)
		int case1 = cur * 10 % k;
		if (dist[cur] < dist[case1]) {
			dist[case1] = dist[cur];
			q.push_front(case1);
		}
 
		// caso 2: sumamos uno a cur pero también incrementamos la suma de dígitos
		int case2 = (cur + 1) % k;
		if (dist[cur] + 1 < dist[case2]) {
			dist[case2] = dist[cur] + 1;
			q.push_back(case2);
		}
	}
 
	// la respuesta debe ser 0 módulo k
	printf("%d\n", dist[0]);
}
from collections import deque
 
k = int(input())
 
# dist[i] = menor suma de dígitos para alcanzar i % k
dist = [float("inf")] * k
q = deque()
 
dist[1] = 1
q.appendleft(1)
 
while q:
	cur = q.popleft()
 
	# caso 1: agregamos un 0 extra al final (SIN COSTO EXTRA)
	case1 = cur * 10 % k
	if dist[cur] < dist[case1]:
		dist[case1] = dist[cur]
		q.appendleft(case1)
 
	# caso 2: sumamos uno a cur pero incrementamos la suma de dígitos
	case2 = (cur + 1) % k
	if dist[cur] + 1 < dist[case2]:
		dist[case2] = dist[cur] + 1
		q.append(case2)
 
# la respuesta debe ser 0 módulo k
print(dist[0])
Fundamentos