Se le proporciona una cadena S de longitud N. La cadena S consta de dígitos del 1 al 9. Considere que la indexación de cadenas está basada en 1.
Debe dividir la cadena en bloques de modo que el iésimo bloque contenga los elementos del índice ((i-1) * X + 1) al min (N, (i * X) (ambos inclusive). Un número es válido si se forma eligiendo exactamente un dígito de cada bloque y colocando los dígitos en el orden de su número de bloque.
Por ejemplo:
Si la cadena dada es '123456789' y X = 3, los bloques formados son [123],[456],[789]. Pocos números válidos son 146.159.348, etc. pero 124 y 396 no son válidos.
Entre todos los números válidos que se pueden formar, tengo que determinar el número K si todos los números válidos únicos se ordenan en orden ascendente.
Mi idea era ordenar cada unobloque h y luego averigua qué número será el número K.
Pero me quedé atascado en cómo encontrar matemáticamente o cualquier otro enfoque el elemento Kth.
def getK(N:int, X:int, K:int, S:str):
from math import ceil
i = 1
N = len(S)
S = list(S)
while i <= ceil(N / X):
start = (i - 1) * X
end = min(N, i * X) - 1
S[start:end+1] = sorted(S[start:end+1])
print(S[start:end+1])
i += 1
print(S)
Por favor, ayúdenme a encontrar una manera de abordar este problema.
------------------------------------
Primero, divide la cadena en bloques:
132 | 444 | 675 | 89
Tenga en cuenta que el último bloque puede tener menos de X dígitos*. También tenga en cuenta que cualquier dígito que elija del segundo bloque, siempre será un 4. Clasifique los bloques y elimine los duplicados**:
123 | 4 | 567 | 89
Ahora, cuando enumeres los números posibles en orden:
1458
1459
1468
1469
1478
1479
2458
...
puedes observar un patrón:
El último dígito cambia con un frefrecuencia de 1, es decir: cada turno.
El segundo pero último dígito cambia con una frecuencia de 2, que es la "duración del ciclo" del último bloque.
Los cambios del tercer pero último dígito tendrían una frecuencia de 6 si hubiera otros dígitos a los que cambiar. Seis es la duración del ciclo de los dos últimos bloques combinados.
El primer dígito cambia con una frecuencia de 6, que es la duración del ciclo combinado de los últimos tres bloques.
Entonces, cuenta las longitudes de los bloques únicos:
3 | 1 | 3 | 2
Para cada bloque, encuentra los productos de los conteos desde ese bloque hasta el final:
18 | 6 | 6 | 2
El primer número es el número total de combinaciones, N. Si k > N, fallo de señal. (Devuelve Ninguno o genera una excepción). De lo contrario, sácalo de la matriz y agrega un 1 al final. Ahora tienes las "frecuencias de actualización" para cada unodígito del canal:
6 | 6 | 2 | 1
Ahora, haga de k un índice de base cero, K = k − 1, porque facilita los cálculos. Digamos que K = 8:
El primer dígito cambia cada sexto número. K div 6 = 1, que es el índice de base cero del número a elegir del primer bloque: "2". Toma el resto de esa división: K ← K mod 6.
El segundo dígito también cambia cada sexto dígito. K div 6 = 0: elija el dígito en el índice 0. (De todos modos, aquí solo hay un dígito, "4"). El resto es 2.
El tercer dígito cambia con cada segundo dígito: K div 2 = 1: elija el dígito en el índice 1: "6". El resto es 0.
El último dígito siempre cambia con cada dígito. Tome el dígito en el índice K = 0: "8"
¿Cuál es el número? ¡2468!
__________
* No necesitas techo de la mosula de matemáticas. YPuedes dividir tus cadenas fácilmente con rango, que también se ocupa de los bloques finales incompletos:
blocks = [s[i:i + X] for i in range(0, n, X)]
** Puedes eliminar entradas duplicadas con un conjunto:
digits = [sorted(set(i)) for i in blocks]
*** Aquí, div significa división entera y mod significa módulo. Los respectivos operadores de Python son // y %: p == (p // q) * q + p % q.
------------------------------------
Basado en el enfoque @M Oem, aquí está mi código para el problema anterior.
def Find_It(N, X, K, S):
S = list(S)
blocks = [S[i:i + X] for i in range(0, N, X)]
digits = [sorted(set(i)) for i in blocks]
freq = [len(x) for x in digits]
for i in range(len(freq) - 2, -1, -1):
freq[i] = freq[i] * freq[i + 1]
if K > freq[0]:
return -1
freq.append(1)
ans = []
K = K - 1
for i in range(1, len(freq)):
div = K // freq[i]
ans.append(digits[i - 1][div])
K = K % freq[i]
print(''.join(ans))
Find_It(11, 3, 9, '13244467589')
Find_It(10, 5, 10, '1234567891')
Output: 2468,29
------------------------------------
Basado en el enfoque @M Oem, aquí está mi código para el problema anterior en C++
void solve(string s, int n, int x, int k) {
vector<string>v;
int idx = 1;
string temp = "";
for (int i = 1; i <= n; i++) {
if (i < min(n, idx*x)) {
temp.push_back(s[i-1]);
}
else {
temp.push_back(s[i-1]);
sort(temp.begin(), temp.end());
// cout << temp << " ";
v.push_back(temp);
temp = "";
idx++;
}
}
int m = v.size();
int arr[m];
for (int i = 0; i < m; i++) {
arr[i] = v[i].length();
}
for (int i = m-2; i >= 0; i--) {
arr[i] = arr[i] * arr[i+1];
// cout << arr[i] << " ";
}
int last = arr[m-1];
for (int i = 0; i < m; i++) {
arr[i] = arr[i] / last;
// cout << arr[i] << " ";
}
string ans = "";
k = k-1; //convert to based 0 index
for (int i = 0; i < m; i++) {
int t = k / arr[i];
string curr = v[i];
ans.push_back(curr[t]);
k = k % arr[i];
// cout << ans << " ";
}
cout << ans << endl;
}
//solve("132456978", 9, 3, 6);
//O/p: 159
