Ranking y unranking P77833


Statement
 

pdf   zip

html

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,

     
  { 25, 50, 75, 100 }          
  { 1, 10, 18, 45 }          
  { 50, 58, 66, 74 }          

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:

     
  {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}.          

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.

Public test cases

  • 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
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++