La idea es resolver este problema utilizando el cálculo previo.
A partir de la declaración, podemos inferir que todos los dígitos deben ser pares (incluido 0 ya que han pedido que no se considere 0 divisible por 11)
Ahora, simplemente intentaremos hacer que cada nuevo número de la lista de números usados agregue uno de los dígitos pares en la parte posterior.
- ¿Cómo se determina la mejor, la media y la peor información dada sobre lo que devuelve un método después del bucle?
- ¿Cuál es la complejidad temporal del montón y el tipo de montón?
- ¿Cuáles son las formas de ajustar algoritmos de aprendizaje automático?
- ¿Cuáles son algunas de las implementaciones de cola (montón) de prioridad más rápida en C ++?
- Cómo encontrar si un número dado es primo o no
Cada vez que lo hacemos, obtenemos un nuevo número y necesitamos probar este número si alguna de sus subcadenas es divisible por 11.
Si es divisible, omitiremos este número; de lo contrario, lo agregaremos a la matriz precalculada.
Por ej. [matemáticas] 2 [/ matemáticas] es un cifrado válido.
Podemos obtener [matemáticas] 20 [/ matemáticas], [matemáticas] 22 [/ matemáticas], [matemáticas] 24 [/ matemáticas], [matemáticas] 26 [/ matemáticas] o [matemáticas] 28 [/ matemáticas] de ella.
Claramente, [math] 22 [/ math] es divisible por [math] 11 [/ math] así que lo descartaremos.
Además, las subcadenas se deben verificar y no solo el nuevo número, es decir
[math] 32 [/ math] es aceptable y podemos obtener [math] 322 [/ math] de él.
Pero, [matemática] 322 [/ matemática] no se toma ya que [matemática] 22 [/ matemática] es una subcadena de la misma, y es divisible por [matemática] 11 [/ matemática].
Ahora, si el número de elementos precalculados excede 1500000, nos separamos.
Nota sobre la implementación:
Al principio puede parecer que podemos iterar sobre todos los números de dígitos pares y solo verificar si ninguna de las subcadenas es divisible por 11.
Pero, esto no debe hacerse.
Considere los números de dígitos pares con prefijo como [math] 22 [/ math].
Dado que este prefijo es divisible por [math] 11 [/ math], todas las cadenas que comiencen con él serán ignoradas y es inútil probarlas.
La idea de implementación correcta es mantener una cola de cifrados válidos y agregar repetidamente dígitos pares en la parte posterior y probar los sufijos de divisibilidad por [math] 11 [/ math].
Algoritmo:
1. Inicialice Q = {0}, cuenta = 0, lim = 1500000, ans = []
2. mientras Q no está vacío:
ttmp: = primer elemento en Q
para i en {0,2,4,6,8}
tmp = ttmp * 10 + i
res = no_suffix_of_tmp_for_divisibility_by_11
si res es verdadero y tmp> 0:
contar ++
ans.add (tmp)
Q.push (tmp)
si cuenta == lim:
break_out_of_while_loop
