Dados dos números A y B, ¿cómo cuenta los números de A a B (inclusive) que no tienen más de dos dígitos repetidos?

Answer 1

Podemos resolver un problema como este usando programación dinámica. Primero veamos el problema simplificado de encontrar el número de números de n dígitos con tal propiedad. Seguiremos agregando dígitos desde la izquierda y solo realizaremos un seguimiento de si hemos repetido el último dígito. Esto significa que solo necesitamos 2 variables. El dígito más a la izquierda puede ser uno de 1-9. Entonces tenemos 10 posibilidades para el siguiente dígito. Nueve de ellos no dan repetición y 1 lo hará. Aquí hay un código de muestra (python) de cómo funciona (si n está definido)

  rep = 0
 norep = 9
 para i en rango (n-1):
     rep, norep = 9 * (rep + norep), rep

 print (rep + norep)

Ahora, si tenemos las restricciones reales como A = 1 y B = 12345, podemos resolver mediante una serie de pasos

1. Primero cuente todos los números de 1,2,3,4 dígitos.
2. Incluya números de 5 dígitos que comiencen con 10___ u 11___
3. Incluya números de 5 dígitos que comiencen con 120___ o 121__ o 122__
4. Incluya números de 5 dígitos que comienzan con 1230_, 1231_, 1232_ o 1233_
5. Incluya los números 12340, 12341, 12342, 12343, 12344, 12345.

Answer 2

Este fue el problema de la ronda universitaria de infosys Aspirations 2020 del 24 de septiembre.

Hay algunos números limitados que violan la condición dada.

Algunos de ellos son:
111,222,333,444,555,666,777,888,999,1000,1111,1222,1333,1444,1555,1666,1777,1888,1999,2222, … etc.

El rango de cualquiera de estos 2 números (cuyo rango tiene más de 20 números) contendrá más de 20 números que no violen la regla.

Así que solo verifique si el rango contiene más de 20 números o no.
Si tiene más de 20 números, lo que ellos llaman “Mágico”,
de lo contrario “No”.

Answer 3

http://codeforces.com/blog/entry/8221
Esto le dará un enfoque concreto para resolver este problema utilizando la programación dinámica.