Ranking y unranking P77833


Statement
 

pdf   zip

thehtml

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 nk 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 x2xk, 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++