Cuente los números sin dígitos repetidos consecutivos -- algorithm campo con c campo con programming-challenge camp codereview Relacionados El problema

Count the numbers without consecutive repeated digits


3
vote

problema

Español

contar los números sin dígitos repetidos consecutivos

Asha ama mucho Matemáticas. Ella siempre pasa su tiempo jugando con dígitos. De repente, ella está atrapada con un problema difícil, que se encuentra a continuación. Ayuda a Asha para resolver este problema mágico de las matemáticas.

Dado un número n (usando cualquier método de entrada estándar), calcule la cantidad de enteros entre 1 y n , inclusive, haga No contiene dos dígitos idénticos consecutivos. Por ejemplo, 1223 debería ser contado , pero se debe contar 121 .

Casos de prueba

  7 => 7 1000 => 819 3456 => 2562 10000 => 7380   

El fragmento de código que presenté para el desafío anterior se proporcionó a continuación

  Option Explicit  Private Sub CommandButton1_Click()     GenerateSqlUserForm.Show End Sub 0  

Cuando presenté el código anterior en la competencia hace unos días, clasificé el primero. Pero ayer no estaba en el 10-11-13 y ahora estoy clasificado 13 en este momento.

¿Cuál fue mi error? ¿Qué debo mejorar para que mi rango sea el primero en la programación competitiva?

Original en ingles

Count the numbers without consecutive repeated digits

Asha loves mathematics a lot. She always spends her time by playing with digits. Suddenly, she is stuck with a hard problem, listed below. Help Asha to solve this magical problem of mathematics.

Given a number N (using any standard input method), compute how many integers between 1 and N, inclusive, do not contain two consecutive identical digits. For example 1223 should not be counted, but 121 should be counted.

Test Cases

7 => 7 1000 => 819 3456 => 2562 10000 => 7380 

The code snippet that i submitted for the above challenge was given below

f(int n) {     int i=1;     int c=n;      for(; i<=n; i++)     {         int m=-1;         int x=i;          while(x)         {             if (x % 10 == m)             {                 c--;                 break;             }             m = x % 10;             x /= 10;        }    }    return c; } 

When I submitted the above code in the competition a few days ago I ranked the First. but yesterday I was at no 10-11-13 and now I am ranked 13 right now.

What was my mistake? What should I improve so that my rank will be the first in competitive programming?

        
     
     

Lista de respuestas

4
 
vote

La declaración del problema da una gran pista: Matemáticas . Así que no la fuerza bruta.

Fije el dígito líder menos que el dígito líder de $ N $ (incluyendo cero). Para el siguiente dígito, tiene 9 opciones (para evitar la repetición). Para el siguiente dígito, nuevamente tiene 9 opciones, etc. El es, cualquier dígito líder menor que el dígito líder de $ N $ le da a los números de $ 9 ^ k $ "buenos".

Con un dígito líder es igual al dígito líder de $ n $, tiene menos opciones, ya que debe permanecer debajo de $ N $. La mejor manera de lidiar es remitir el dígito líder de $ N $, y aplicar la misma lógica al número restante.

Por ejemplo, para $ n = 3456 $ funciona así, $ 3 veces 9 ^ 3 + 4 veces 9 ^ 2 + 5 veces 9 + 6 = 2562 $

ahora convertirlo al código.

Sugerencia: También puede ir a la izquierda.

 

The problem statement gives a great hint: mathematics. So do not brute force.

Fix the leading digit less than the leading digit of \$N\$ (including zero). For the next digit you have 9 choices (to avoid repetition). For the next digit you again have 9 choices, etc. The is, any leading digit less than the leading digit of \$N\$ gives \$9^k\$ "good" numbers.

With a leading digit equals to leading digit of \$N\$ you have less choices, because you have to stay below \$N\$. The best way to deal with is is to remove the leading digit of \$N\$, and apply the same logic to the remaining number.

For example, for \$N=3456\$ it works like this \$3 \times 9^3 + 4 \times 9^2 + 5 \times 9 + 6 = 2562\$

Now convert it to the code.

Hint: you can also go right to left.

 
 

Relacionados problema

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos