Digit Queries

Explicación

Nótese que esto es bastante tramposo para un problema de Bronce.

Como $k$ puede ser tan grande como $10^{18}$, no hay forma de abordar este problema por fuerza bruta. En su lugar, necesitaremos elaborar un algoritmo que pueda responder consultas en tiempo logarítmico.

Agrupemos los números según cuántos dígitos tienen. Una observación que podemos hacer es que para cualquier $n \geq 1$, hay $9 \cdot 10^{n-1}$ números en el grupo con números de longitud $n$. Además, para cada grupo, el recuento total de dígitos de todos los números del grupo combinados es $n$ veces cuántos números hay en el grupo. Por ejemplo:

• Números de longitud $1$: $1\dots 9\rightarrow$ $9$ números $\rightarrow1\cdot9=9$ dígitos en total
• Números de longitud $2$: $10\dots 99\rightarrow$ $90$ números $\rightarrow2\cdot90=180$ dígitos en total
• Números de longitud $3$: $100\dots 999\rightarrow$ $900$ números $\rightarrow3\cdot900=2700$ dígitos en total
• Y así sucesivamente…

Para hallar en qué grupo está el número que contiene el $k$-ésimo dígito, podemos iterar por los grupos hasta que la suma del número total de dígitos de todos los grupos que hemos procesado sea mayor o igual que $k$. En otras palabras, seguimos aumentando el número de grupos que miramos (empezando por los números de $1$ dígito) hasta que se cumpla lo siguiente:

Una vez que la condición se vuelve verdadera, sabemos que el $k$-ésimo dígito debe caer en el último grupo usado en la suma. Ahora podemos calcular la posición del $k$-ésimo dígito en el grupo restando a $k$ el número total de dígitos de todos los grupos anteriores. Llamaremos a esta posición relativa $j$:

Nótese que restamos $1$ del resultado para que $j$ quede indexado desde $0$ (lo que hace más conveniente resolver el resto del problema). Por ejemplo, si $j=0$, eso significaría que el $k$-ésimo dígito es el primer dígito del grupo. Si $j=100$, eso significaría que el $k$-ésimo dígito es el dígito $99$-ésimo del grupo, etc. A partir de ahí, podemos dividir $j$ por $n$ (la longitud de los números del grupo), lo que nos da la posición del número que contiene el $k$-ésimo dígito dentro del grupo (también indexada desde $0$). De forma similar a antes, una posición de $0$ significa que el número es el primer número del grupo, y una posición de $100$ significa que el número es el $99$-ésimo número del grupo.

Para calcular el número exacto en el que está el $k$-ésimo dígito, podemos sumar la posición del número dentro del grupo (que acabamos de hallar) al valor del primer número del grupo, que es simplemente $10^{n-1}$ (se puede ver este patrón en el ejemplo del principio). Ahora, solo queda hallar la posición del $k$-ésimo dígito dentro del número en el que está. Podemos calcularla tomando $j \bmod n$, que halla el resto de $j$ al dividirlo por $n$. Por ejemplo, miremos los primeros $12$ dígitos del grupo de números de longitud $3$:

Como se puede ver, para cada número de $3$ dígitos en la secuencia de dígitos, el primer dígito está siempre en una posición que es múltiplo de $3$, lo que significa que la posición módulo $3$ es igual a $0$. De forma similar, el segundo dígito de cada número está siempre en una posición que es $1$ más un múltiplo de $3$, lo que significa que su posición módulo $3$ es igual a $1$. Por último, el tercer dígito de cada número es siempre $2$ más un múltiplo de $3$, lo que significa que su posición módulo $3$ es igual a $2$. Este patrón se extiende a números de todos los tamaños, y por eso podemos usar el operador módulo para determinar la posición indexada desde $0$ del $k$-ésimo dígito dentro del número en el que está.

Ahora, podemos calcular nuestra respuesta convirtiendo el número en el que está el $k$-ésimo dígito en un string e indexándolo en la posición que acabamos de hallar.

Implementación

Complejidad temporal: $\mathcal{O}(q\log{k})$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Devuelve 10 elevado a la potencia de "exp"
// No usamos pow() porque puede ser inexacto para potencias grandes
ll pow10(int exp) {
	ll product = 1;
	for (int i = 0; i < exp; i++) { product *= 10; }
	return product;
}
 
int main() {
	int q;
	ll k;
	cin >> q;
 
	for (int i = 0; i < q; i++) {
		cin >> k;
		/*
		 * Restamos a k los tamaños de los grupos hasta que k sea menor que el tamaño
		 * del grupo actual. Esto produce el mismo efecto que sumar los tamaños de los
		 * grupos hasta que k sea menor o igual que la suma. Para cuando
		 * el bucle while termina, k - 1 será igual a j.
		 */
		int n = 1;
		while (k > n * 9 * pow10(n - 1)) {
			k -= n * 9 * pow10(n - 1);
			n++;
		}
 
		// El número exacto en el que está el k-ésimo dígito
		long num = (k - 1) / n + pow10(n - 1);
		// La ubicación en num del k-ésimo dígito
		int loc = (int)((k - 1) % n);
		// Determinamos la respuesta convirtiendo num a string e indexando en loc
		cout << to_string(num)[loc] << endl;
	}
}

import java.io.*;
import java.util.*;
 
public class DigitQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int q = io.nextInt();
		for (int i = 0; i < q; i++) {
			long k = io.nextLong();
			/*
			 * Restamos a k los tamaños de los grupos hasta que k sea menor que el
			 * tamaño del grupo actual. Esto produce el mismo efecto que
			 * sumar los tamaños de los grupos hasta que k sea menor o igual que la
			 * suma. Para cuando el bucle while termina, k - 1 será igual a j.
			 */
			int n = 1;
			while (k > n * 9 * pow10(n - 1)) {
				k -= n * 9 * pow10(n - 1);
				n++;
			}
 
			// El número exacto en el que está el k-ésimo dígito
			long num = (k - 1) / n + pow10(n - 1);
			// La ubicación en num del k-ésimo dígito
			int loc = (int)((k - 1) % n);
			// Determinamos la respuesta convirtiendo num a string e indexando en loc
			io.println(Long.toString(num).charAt(loc));
		}
		io.close();
	}
 
	// Devuelve 10 elevado a la potencia de "exp"
	// No usamos Math.pow() porque puede ser inexacto para potencias grandes
	static long pow10(int exp) {
		long product = 1;
		for (int i = 0; i < exp; i++) { product *= 10; }
		return product;
	}
 
	// CodeSnip{Kattio}
}

for _ in range(int(input())):
	k = int(input())
	"""
	Restamos a k los tamaños de los grupos hasta que k sea menor que el tamaño del
	grupo actual. Esto produce el mismo efecto que sumar los tamaños de los grupos hasta
	que k sea menor o igual que la suma. Para cuando el bucle while termina,
	k - 1 será igual a j.
	"""
	n = 1
	while k > n * 9 * 10 ** (n - 1):
		k -= n * 9 * 10 ** (n - 1)
		n += 1
 
	# El número exacto en el que está el k-ésimo dígito
	num = (k - 1) // n + 10 ** (n - 1)
	# La ubicación en num del k-ésimo dígito
	loc = (k - 1) % n
	# Determinamos la respuesta convirtiendo num a string e indexando en loc
	print(str(num)[loc])