1120 - Number Sequence

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
dovier
Posts: 1143
Joined: 7 years ago
Location: Havana, Cuba
Gender: Male
Cuba

1120 - Number Sequence

Post by dovier » 7 years ago




User avatar
Dariel
Posts: 51
Joined: 7 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 1120 - Number Sequence

Post by Dariel » 3 years ago

Alguna idea de como solucionar este problema...

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 1120 - Number Sequence

Post by humbertodiaz » 3 years ago

Saludos Dariel. No hemos estado en contacto en un tiempo asi que es bueno ver que todavia estas resolviendo ejercicios.

Parece que no he resuelto este problema antes. Mi idea seria hacerlo un poco a fuerza bruta debido a que no habran tantos casos para resolver a la vez. La secuencia de digitos S consiste de los numeros desde 1 hasta N concatenados, primero con N = 1, despues N = 2, y asi continua infinitamente. Yo encontraria una manera de calcular el largo de esa concatenacion para un valor de N particular. Digamos que tenemos una funcion F(N) que nos dice cuantos digitos tienen los primeros N numeros cuando se concatenan. Entonces la podriamos usar para saber en que segmento de numeros cae el indice K que nos dan.

Por ejemplo, si nos dan K = 9...
F(1) = 1, que es menor que 9, asi que el digito que nos interesa esta mas lejos. Podemos repetir esto, pero con K = 9 - 1 = 8, y N = 2.
F(2) = 2, que es menor que 8. Reasignamos K = 8 - 2 = 6, y N = 3.
F(3) = 3, que es menor que 6. Reasignamos K = 6 - 3 = 3, y N = 4.
F(4) = 4. Como K <= F(4), nuestro indice apunta a un digito en este segmento. Seria el tercer digito en la concatenacion de los numeros 1 hasta 4: "1234"

El resultado seria 3.

Hay varias formas de hacer esto eficiente para que se pueda evaluar F(N) rapidamente. Considera que estamos evaluando F(N) para numeros consecutivos (1, 2, 3, ...), asi que se puede mantener una suma o se pueden precalcular los valores. Quedaria el paso de encontrar cual es el digito que nos interesa cuando K <= F(N).

Espero que esto te ayude.

Post Reply

Return to “Problem set”