Codificación aritmética P37123


Statement
 

pdf   zip

thehtml

Considera un alfabeto Σ donde cada letra ci tiene asociado una probabilidad pi. Por ejemplo, Σ={c1=A, c2=B, c3=C} con

p(A) = p1 = 
1
2
,    p(B) = p2 = 
1
5
    p(C) = p3 = 
3
10

A cada palabra (secuencia de letras) s del alfabeto Σ le asignamos un intervalo I(s)=[a;b) según las reglas siguientes.

  • El intervalo de la palabra vacía s=λ es
    I(λ)=[0; 1). 
  • El intervalo de la palabra s=t· ci, donde t es una palabra con I(t)=[a; b) y ci es la última letra de s, es
    I(s)=[a + (p1 + ⋯ + pi−1)·(ba); a + (p1 + ⋯ + pi)·(ba)).

Por ejemplo, a las palabras λ, A, AA, AAC, AACB les corresponden los siguientes intervalos:

     
I(λ)= [0; 1)          
I(A)= [0 + 0· 1; 0 + 0.5 · 1) = [0; 0.5)          
I(AA)= [0 + 0 · 0.5; 0 + 0.5 · 0.5) = [0; 0.25)          
I(AAC)= [0 + 0.7 · 0.25; 0 + 1 · 0.25) =[0.175; 0.25)          
I(AACB)= [0.175 + 0.5 · 0.075; 0.175 + 0.7 · 0.075) = [0.2125; 0.2275)          

Cuantas más letras añadimos, más pequeño es el intervalo resultante.

Entrada

Una línea con el número n de letras del alfabeto. A continuación, n líneas con las letras ci del alfabeto y las probabilidades pi de cada letra. Todas las probabilidades cumplen pi≥ 0.1 y se te garantiza que p1 + ⋯ + pn = 1.

Por último, un número indeterminado de líneas con los casos de prueba. Cada caso de pruebas es un número natural k<6 y un número real r entre 0 y 1.

Salida

Para cada caso, escribe la única palabra s de k letras cuyo intervalo I(s) contiene el real r. Se te garantiza que las entradas serán tales que nunca tendrás problemas de precisión usando double.

Public test cases
  • Input

    2
    A 0.5
    B 0.5
    1 0.25
    1 0.75
    0 0.5
    2 0.99
    5 0.7501
    5 0.7499
    

    Output

    A
    B
    
    BB
    BBAAA
    BABBB
    
  • Input

    3
    A 0.5
    B 0.2
    C 0.3
    4 0.2124
    4 0.2126
    4 0.2274
    4 0.2276
    4 0.9999
    4 0.9
    

    Output

    AACA
    AACB
    AACB
    AACC
    CCCC
    CBCA
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++