Ranking y unranking P77833
Se quiere transmitir un subconjunto de k elementos de {1, …, n} tal que ningún par de elementos está a distancia menor de t. Por ejemplo, para k=4, n=100 y t=8, los siguientes son subconjuntos válidos,
|
pero el subconjunto {5, 45, 52, 100} no es válido puesto que 52 − 45 = 7, que es menor que t=8.
Hay varios modos posibles de codificar conjuntos semejantes: por ejemplo, podríamos usar n bits para decir, para cada elemento, si está o no en el conjunto; o podríamos usar k números de log2n bits para dar la lista de los elementos que están dentro (o n−k números para dar la lista de los que están fuera). Pero la codificación más eficiente de todas, para cualquier combinación de n, k y t, es el proceso conocido como ranking. Para codificiar un conjunto, se hace lo siguiente:
- Se generan (en orden lexicográfico, y con los elementos del conjunto ordenados crecientemente) una lista con todos los subconjuntos posibles para los valores dados de n, k y t.
- Se localiza nuestro subconjunto dentro de la lista.
- La codificación es la posición del conjunto dentro de la lista.
Por ejemplo, para n=11, k=3, t=4, la lista ordenada de subconjuntos válidos es:
|
En este caso, el subconjunto {2, 6, 10} se codificaría (ranking) como 7, mientras que la decodificación (unranking) del número 4 sería el subconjunto {1, 6, 10}.
Se te pide que hagas un programa que sepa codificar y descodificar conjuntos siguiendo el proceso anterior.
Entrada
Una línea con 3 números n, k y t, separados por espacios. Se cumple que n≤ 100 y que el número de subconjuntos válidos no es mayor que 1018. A continuación, un número arbitrario de líneas de la forma C x1 x2 ⋯ xk, donde {x1, …, xk} es un subconjunto válido con x1<⋯<xk, o de la forma D s, donde s es un número entre 1 y el número de subconjuntos válidos.
Salida
Escribe una línea con la codificación de {x1, …, xk} (si la entrada empieza por C) o la descodificación de s (con los elementos del subconjunto ordenados y separados por espacios) si la entrada empieza por D.
Pista No es necesario (ni deseable, a menos que n sea pequeña) generar todos los subconjuntos válidos para hacer el ranking y el unranking.
Puntuación
- TestA: 25 Puntos
Entradas donde todos los casos empiezan por C y n≤ 12, como el ejemplo 1.
- TestB: 25 Puntos
Entradas donde todos los casos empiezan por D y n≤ 10, como el ejemplo 2.
- TestC: 25 Puntos
Entradas donde todos los casos empiezan por C.
- TestD: 25 Puntos
Entradas donde todos los casos empiezan por D.
Input
11 3 4 C 1 5 9 C 1 5 10 C 1 5 11 C 1 6 10 C 1 6 11 C 1 7 11 C 2 6 10 C 2 6 11 C 2 7 11 C 3 7 11
Output
1 2 3 4 5 6 7 8 9 10
Input
11 3 4 D 1 D 2 D 3 D 4 D 5 D 6 D 7 D 8 D 9 D 10
Output
1 5 9 1 5 10 1 5 11 1 6 10 1 6 11 1 7 11 2 6 10 2 6 11 2 7 11 3 7 11
Input
100 8 6 C 1 7 13 19 25 31 37 43 C 58 64 70 76 82 88 94 100 C 20 30 50 60 70 80 90 100
Output
1 5047381560 4812990706
Input
100 8 6 D 1 D 5047381560 D 4812990706
Output
1 7 13 19 25 31 37 43 58 64 70 76 82 88 94 100 20 30 50 60 70 80 90 100
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++