Ranking y unranking P77833

Se quiere transmitir un subconjunto de $k$ elementos de $\{1, \ldots, 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, $$\begin{align*} & \{ 25, 50, 75, 100 \} \\ & \{ 1, 10, 18, 45 \} \\ & \{ 50, 58, 66, 74 \} \end{align*}$$ 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 $\log_2{n}$ 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: $$\begin{align*} & \{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\}. \end{align*}$$ 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\le 100$ y que el número de subconjuntos válidos no es mayor que $10^{18}$. A continuación, un número arbitrario de líneas de la forma C $x_1 x_2 \cdots x_k$, donde $\{x_1, \ldots, x_k\}$ es un subconjunto válido con $x_1<\cdots<x_k$, 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 $\{x_1, \ldots, x_k\}$ (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:

  Entradas donde todos los casos empiezan por C y $n\le 12$, como el ejemplo 1.

• TestB:

  Entradas donde todos los casos empiezan por D y $n\le 10$, como el ejemplo 2.

• TestC:

  Entradas donde todos los casos empiezan por C.

• TestD:

  Entradas donde todos los casos empiezan por D.