Codigos ambiguos P51767


Statement
 

pdf   zip

thehtml

Una palabra formada por letras minúsculas (las 26 del alfabeto inglés, entre ‘a’ y ‘z’, sin acentos) puede ser codificada usando dígitos de la manera siguiente: reemplazamos cada ‘a’ por “1”, cada ‘b’ por “2”, …, cada ‘i’ por “9”, cada ‘j’ por “10”, …, cada ‘s’ por “19”, cada ‘t’ por “20”, …, y cada ‘z’ por “26”. Así, por ejemplo, el código de la palabra “pan” sería “16114”.

Lamentablemente, esta codificación en general es ambigua, puesto que más de una palabra puede compartir el mismo código. Siguiendo con el ejemplo, tanto “afan”, como “afaad”, como alguna otra palabra (con o sin sentido) también tendría código “16114”. Sin embargo, hay códigos que son inambiguos. Por ejemplo, “29” sólo puede ser el código de “bi”, y “1010” sólo puede ser el código de “jj”.

Vuestra tarea es hacer un programa que escriba los p primeros códigos de n dígitos.

Entrada

La entrada consiste en un natural n, seguido de un carácter c, seguido de un natural p.

Salida

Vuestro programa debe escribir, en orden y uno por línea, los p primeros códigos de n dígitos. Si c es una ‘t’, debéis escribir los p primeros de todos los códigos, ambiguos o no. Si c es una ‘i’, debéis escribir los p primeros códigos inambiguos. Podéis suponer que p siempre estará entre 1 y el número de códigos totales o inambiguos, según sea el caso.

Observación

Este problema tiene juegos de prueba donde la salida puede ser muy grande (105 líneas). Si programas en C++, usa "\n" en vez de endl para escribir el salto de línea; en caso contrario, tu programa no tendrá tiempo de escribir toda la salida en el entorno en el que el juez se ejecuta.

Puntuación

  • TestA:  ‍30 Puntos ‍

    Casos donde n está entre 1 y 5, c es ‘t’, y p es exactamente el número total de códigos de n dígitos.

  • TestB:  ‍30 Puntos ‍

    Casos donde n está entre 1 y 5, c es ‘i’, y p es exactamente el número de códigos inambiguos de n dígitos.

  • TestC:  ‍40 Puntos ‍

    Casos donde n está entre 1 y 8, c es ‘i’ o ‘t’, y p es como mucho 105.

Public test cases
  • Input

    2 t 10
    

    Output

    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
  • Input

    2 i 8
    

    Output

    10
    20
    27
    28
    29
    31
    32
    33
    
  • Input

    5 i 15
    

    Output

    10101
    10102
    10103
    10104
    10105
    10106
    10107
    10108
    10109
    10110
    10120
    10201
    10202
    10203
    10204
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++